Paper 2024/510
DoS-resistant Oblivious Message Retrieval from Snake-eye Resistant PKE
Abstract
Oblivious message retrieval (OMR) allows messages resource-limited recipients to outsource the message retrieval process without revealing which messages are pertinent to which recipient. Its realizations in recent works leave an open problem: can an OMR scheme be both practical and provably secure against spamming attacks from malicious senders (i.e., DoS-resistant) under standard assumptions? In this paper, we first prove that a prior construction OMRp2 is DoS-resistant under a standard LWE assumption, resolving an open conjecture of prior works. Then, we present DoS-PerfOMR: a provably DoS-resistant OMR construction that is 12x faster than OMRp2, and (almost) matches the performance of the state-of-the-art OMR scheme that is not DoS-resistant. As a building block, we analyze the snake-eye resistance property for general PKE schemes. We construct a new lattice-based PKE scheme, LWEmongrass that is provably snake-eye resistant and has better efficiency than the PVW scheme underlying OMRp2. We also show that the natural candidates (e.g., RingLWE PKE) are not snake-eye resistant. Of independent interest, we introduce two variants of LWE with side information, as components towards proving the properties of LWEmongrass, and reduce standard LWE to them for the parameters of interest.
Metadata
- Available format(s)
- Publication info
- Preprint.
- Keywords
- Oblivious Message RetrievalLattice-based CryptographyFully Homomorphic Encryption
- Contact author(s)
-
zeyu liu @ yale edu
katerina sotiraki @ yale edu
eprint2eran @ tromer org
yunhao wang @ yale edu - History
- 2024-04-01: approved
- 2024-03-31: received
- See all versions
- Short URL
- https://ia.cr/2024/510
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/510, author = {Zeyu Liu and Katerina Sotiraki and Eran Tromer and Yunhao Wang}, title = {DoS-resistant Oblivious Message Retrieval from Snake-eye Resistant PKE}, howpublished = {Cryptology ePrint Archive, Paper 2024/510}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/510}}, url = {https://eprint.iacr.org/2024/510} }