First, regarding acknowledgements: the job of cryptography is not only to keep secrets, but also to ensure that the receiver got the full message exactly as we intended to, with nothing left out. Being able to detect if something is left out can be crucial. Same with unpredictable ordering. Den 3 nov 2015 18:52 skrev "Jeff Burdges" <<a href="mailto:burdges@gnunet.org">burdges@gnunet.org</a>>: > > On Tue, 2015-11-03 at 17:00 +0100, Ximin Luo wrote: > > > There are a bunch of reasons for using a limited pool of tokens to > > > authenticate delivery. I'd imagine such systems might be slow to > > retry > > > dropped messages to avoid waisting the tokens, and they'd likely > > burn > > > several tokens before complaining that the message dropped, so > > you've > > > potentially hours of delay before the system colors your message as > > > dropped. > > > > Not sure why you need a limited pool of tokens to authenticate > > delivery? > > There are not many systems that satisfy both M0/M1 and R0 from : > > <a href="http://www.lothar.com/blog/53-petmail-delivery/">http://www.lothar.com/blog/53-petmail-delivery/</a> [...] So the requirements as you see them are these: * that each sender gets a token from the receiver that let them tell the receiver AND the server that there's a valid message, but that only tell the receiver from who. * that the receiver can revoke / blacklist individual tokens reasonably efficiently So the message tags must be verifiable yet unlinkable to any other if you lack the tokens, but revealing some knowledge/secret to the server or replacing some verifier accessible to the server should let it filter out revoked tokens. Efficient Zero-knowledge proofs would make it easy. Compute a Merkle tree hash (verifier) of the valid per-sender tokens (multi-use), let them HMAC each message with with the tokens and provide a ZKP (unlinkable proof) for that the token used in the HMAC is in the latest Merkle tree hash and that the HMAC was computed from the message ciphertext. Revoke by either telling the server the token for a quick blacklist (easy to do from the phone when you don't have your full token list ready to create a new Merkle tree hash), or replace the Merkle tree hash. This still let the senders know the receiver is the same person (same Merkle tree hash). Another approach that I came to think of but don't know if it is possible is to have some RNG-like key derivation algorithm where having the full original seed let you compute a certain set of keys/tokens, and any subset / derivation of that seed generates different (non-overlapping) subsets of this set of keys. I came to think of this variant by thinking of Bitcoin hierarchical deterministic wallets with hardened derivation as well as this: Even more practical secure logging: Tree-based Seekable Sequential Key Generators - <a href="https://eprint.iacr.org/2014/479">https://eprint.iacr.org/2014/479</a> Maybe something could be done with ECC math for this? Or with threshold cryptography? Lattice cryptography? The idea is that only I know what sub-seeds I derived from the full seed, not the server, and the senders know their sub-seeds but not the full seed. But I can tell the server what sub-seeds whose numbers to reject. If possible, this is simpler than ZKP by far, but also need "refills" unless the RNG essentially can go on forever and you can shift the allowed range of outputs forwards by time to limit the set of permissible keys at any point in time. May also need replacement if you issue too many sub-seeds to avoid overlap in outputs. Monero also has some various ECDSA based key derivation and ring signature algorithms to hide senders and receivers. Look up what they do. There's also *selectively* linkable / accountable / traceable ring signatures, where the receiver creates all the sender keypairs and creates a ring public key from them all. A per-keypair secret is revealed to enable accountability = linking together messages signed by the same keypair, allowing for blacklisting. You can easily derive hundreds of keys in advance (using a KDF and a seed you remember saves space), and each key can be reused by the sender (until blacklisted). Can't find any good resources right now though. Another relevant system is libforwardsec: <a href="https://github.com/imichaelmiers/libforwardsec/">https://github.com/imichaelmiers/libforwardsec/</a> They combine Identity Based Encryption (IBE) that provides one (individually deletable) private keys per each time interval with a puncturable algorithm that provides the ability to revoke your decryption capability for any given set of messages, and lets you create a single public key for it. If nothing else it will improve the deniability for receivers. After the first message per sender-receiver pair you can move on to an axolotl style key ratchet.