Paper 2024/204
PerfOMR: Oblivious Message Retrieval with Reduced Communication and Computation
Abstract
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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. USENIX Security 2024
- Keywords
- Oblivious message retrievalAnonymous message deliveryFully homomorphic encryption
- Contact author(s)
-
zeyu liu @ yale edu
eprint2eran @ tromer org
yunhao wang @ yale edu - History
- 2024-06-07: last of 2 revisions
- 2024-02-09: received
- See all versions
- Short URL
- https://ia.cr/2024/204
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/204, 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}, url = {https://eprint.iacr.org/2024/204} }