Speaker: Zeyu Liu, Yale University

Title: Recent Advancements in Single-Server Oblivious Message Retrieval

Abstract: Anonymous message delivery systems, such as private messaging services and privacy-preserving blockchains, require mechanisms that allow recipients to retrieve messages addressed to them without leaking metadata or enabling message linkage. A simple approach is for recipients to download all posted messages and locally scan for those addressed to them, but this becomes prohibitively expensive in terms of communication and computation at scale.

We show how untrusted servers can detect messages on behalf of recipients and aggregate them into a compact encrypted digest that recipients can efficiently decrypt, via the cryptographic primitive Oblivious Message Retrieval. These servers operate obliviously and learn nothing about which messages are addressed to which recipients. Privacy, soundness, and completeness are guaranteed even if all parties except the recipient are adversarial and colluding. Moreover, our model and constructions generalize naturally to group messaging or mailing lists, where senders can generate messages that are efficiently detectable by multiple designated recipients.

In this talk, we begin with an asymptotically efficient construction based on Fully Homomorphic Encryption and homomorphically encoded Sparse Random Linear Codes. We then discuss recent advancements that lead to concretely efficient instantiations of this paradigm. Finally, we address additional security considerations, including resilience to denial-of-service attacks.

Bio: Zeyu Liu is a PhD student at Yale University, advised by Ben Fisch. He received his MS from Columbia University, where he was advised by Tal Malkin and Eran Tromer. His research focuses on cryptography, including fully homomorphic encryption, metadata privacy, and lattice-based cryptography.