Anonymous message delivery systems, such as private messaging services and privacy-preserving blockchains, need a mechanism for recipients to retrieve the messages addressed to them, without leaking metadata or letting their messages be linked. Recipients could download all posted messages and scan for those addressed to them, but communication and computation costs are excessive at scale.

We show how untrusted servers can detect messages on behalf of recipients, and summarize these into a compact encrypted digest that recipients can easily decrypt. These servers operate obliviously and do not learn anything about which messages are addressed to which recipients. Privacy, soundness, and completeness hold even if everyone but the recipient is adversarial and colluding.

Furthermore, the model and constructions generalize to the setting of group messaging or mailing lists: senders can generate messages that would be efficiently detected by multiple recipients of their choice.

Our starting point is an asymptotically-efficient approach, using Fully Homomorphic Encryption and homomorphically-encoded Sparse Random Linear Codes. We then address the concrete performance using bespoke tailoring of lattice-based cryptographic components, alongside various algebraic and algorithmic optimizations. This reduces the digest size to a few bits per message scanned. Concretely, the servers’ cost is <$0.1 per million messages scanned, and the resulting digests can be decoded by recipients in ~20ms. Our schemes can thus practically attain the strongest form of receiver privacy for current applications such as privacy-preserving cryptocurrencies.

We also consider the case of group messaging, where each message may have multiple recipients (e.g., in a group chat or blockchain transaction). We devise new protocols where the servers' cost grows very slowly with the group size, while recipients' cost is low and independent of the group size.

(Will cover https://eprint.iacr.org/2021/1256, https://eprint.iacr.org/2023/534, and https://eprint.iacr.org/2024/204 if time permits. Will focus one the first one.)

Zeyu Liu is a third year PhD student at Yale University, advised by Prof. Ben Fisch. His main research interests lie in the general area of cryptography, including lattice-based cryptography, blockchain-based cryptographic protocols, and so on. He obtained his MS at Columbia University advised by Prof. Tal Malkin and Prof. Eran Tromer and his Bachelor's degree at UCLA. His works are mainly published in cryptography-related conferences (e.g., Crypto, Asiacrypt, CCS, Usenix Security, S&P).