Oblivious Message Retrieval: Foundations and Recent Advances

Lunch will be available at 11:45am.

Title:

Oblivious Message Retrieval: Foundations and Recent Advances

Abstract:

Protecting the contents of a message is only part of private communication: revealing who communicates with whom can also expose sensitive information. Anonymous message delivery systems, including private messaging services and privacy-preserving blockchains, therefore need ways for users to retrieve their messages without revealing which messages belong to them. A simple solution is for every user to download all posted messages and identify their own locally, but this becomes prohibitively expensive as the message board size grows.

Oblivious message retrieval (OMR) offers a more efficient alternative. It enables untrusted servers to find messages on behalf of a recipient and combine them into a compact encrypted digest, without learning which messages are intended for that recipient. The recipient can then efficiently download and decrypt the digest to recover their messages, rather than downloading and scanning the entire board. Crucially, OMR provides privacy, soundness, and completeness guarantees even when all parties other than the recipient are adversarial and collude.

This talk surveys the foundations of OMR and recent advances that improve its practical efficiency and address key deployment challenges. We begin with an asymptotically efficient construction based on fully homomorphic encryption and homomorphically encoded sparse random linear codes. We then explore the techniques that make this approach concretely efficient. Finally, we discuss security and deployment considerations, including resilience to denial-of-service attacks, identity hiding, and support for group messaging, where a single message is addressed to multiple recipients.

Bio:

Zeyu Liu is a final-year Ph.D. student in Computer Science at Yale University, advised by Ben Fisch. He received his M.S. from Columbia University, where he was advised by Tal Malkin and Eran Tromer, and his B.S. from UCLA. His research focuses on cryptography, with particular interests in fully homomorphic encryption, metadata privacy, and lattice-based cryptography. More information about his research is available on his website (https://zeyuthomasliu.github.io/).