Paper 2024/204

PerfOMR: Oblivious Message Retrieval with Reduced Communication and Computation

Zeyu Liu, Yale University
Eran Tromer, Boston University
Yunhao Wang, Yale University
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. This exhibits significant costs in computation per message scanned (${\sim}109$ms), 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 more efficiently. Concretely, this construction takes only ${\sim}7.3$ms per message scanned, about $15$x faster than the prior work. The second protocol focuses on reducing the communication costs, by designing a different homomorphic decryption circuit. While the circuit is less homomorphic-encryption-friendly (than our first construction), it allows the parameter of the Ring-LWE encryption to be set such that both the public key and the message size are greatly reduced. Concretely, 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.

Metadata
Available format(s)
PDF
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-02-12: approved
2024-02-09: received
See all versions
Short URL
https://ia.cr/2024/204
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2024/204}},
      url = {https://eprint.iacr.org/2024/204}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.