Paper 2024/510

Snake-eye Resistant PKE from LWE for Oblivious Message Retrieval and Robust Encryption

Abstract

Oblivious message retrieval (OMR) allows 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 $$ is DoS-resistant under a standard LWE assumption, resolving an open conjecture of prior works. Then, we present $$: a provably DoS-resistant OMR construction that is 12x faster than $$, and (almost) matches the performance of the state-of-the-art OMR scheme that is $$ DoS-resistant (proven by the attacks we show). To achieve this, we analyze the $$ property for general PKE schemes (i.e., it is hard to encrypt an identical message under two keys). We construct a new lattice-based PKE scheme: $$, that is provably snake-eye resistant and has better efficiency than the PVW scheme underlying $$. We also show that the natural candidates (e.g., RingLWE PKE) are not snake-eye resistant. Furthermore, we show that a snake-eye resistant PKE scheme implies a robust PKE scheme, thus introducing the first robust lattice-based PKE scheme without relying on the KEM-DEM paradigm and its inherent inefficiencies. Of independent interest, we introduce two variants of LWE with side information, as components towards proving the properties of $$, and reduce standard LWE to them for the parameters of interest.

Note: 02/07/2025: Made some editorial changes to the title and main texts. 08/20/2024: Made some editorial changes to the title, abstract, and main texts. 06/07&08/2024: Added the relation to robust encryption; made some editorial changes.