Paper 2024/510

DoS-resistant Oblivious Message Retrieval from Snake-eye Resistant PKE

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

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.

Available format(s)
Publication info
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
2024-04-01: approved
2024-03-31: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.