Paper 2024/204

PerfOMR: Oblivious Message Retrieval with Reduced Communication and Computation

Zeyu Liu, Yale University
Eran Tromer, Boston University
Yunhao Wang, Yale University

Anonymous message delivery, as in privacy-preserving blockchain and private messaging applications, needs to protect recipient metadata: eavesdroppers should not be able to link messages to their recipients. This raises the question: how can untrusted servers assist in delivering the pertinent messages to each recipient, without learning which messages are addressed to whom? Recent work constructed Oblivious Message Retrieval (OMR) protocols that outsource the message detection and retrieval in a privacy-preserving way, using homomorphic encryption. Their construction exhibits significant costs in computation per message scanned (${\sim}0.1$ second), as well as in the size of the associated messages (${\sim}1$kB overhead) and public keys (${\sim}132$kB). This work constructs more efficient OMR schemes, by replacing the LWE-based clue encryption of prior works with a Ring-LWE variant, and utilizing the resulting flexibility to improve several components of the scheme. We thus devise, analyze, and benchmark two protocols: The first protocol focuses on improving the detector runtime, using a new retrieval circuit that can be homomorphically evaluated $15$x faster than the prior work. The second protocol focuses on reducing the communication costs, by designing a different homomorphic decryption circuit that allows the parameter of the Ring-LWE encryption to be set such that the public key size is about $235$x smaller than the prior work, and the message size is roughly $1.6$x smaller. The runtime of this second construction is ${\sim}40.0$ms per message, still more than $2.5$x faster than prior works.

Note: Fixed some typos and added the link for the open-sourced code.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. USENIX Security 2024
Oblivious message retrievalAnonymous message deliveryFully homomorphic encryption
Contact author(s)
zeyu liu @ yale edu
eprint2eran @ tromer org
yunhao wang @ yale edu
2024-03-24: revised
2024-02-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zeyu Liu and Eran Tromer and Yunhao Wang},
      title = {PerfOMR: Oblivious Message Retrieval with Reduced Communication and Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2024/204},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.