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

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 $\mathsf{OMRp2}$ is DoS-resistant under a standard LWE assumption, resolving an open conjecture of prior works. Then, we present $\mathsf{DoS\text{-}PerfOMR}$: a provably DoS-resistant OMR construction that is 12x faster than $\mathsf{OMRp2}$, and (almost) matches the performance of the state-of-the-art OMR scheme that is $\textit{not}$ DoS-resistant (proven by the attacks we show).

To achieve this, we analyze the $\textit{snake-eye resistance}$ 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: $\mathsf{LWEmongrass}$, that is provably snake-eye resistant and has better efficiency than the PVW scheme underlying $\mathsf{OMRp2}$. 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 $\mathsf{LWEmongrass}$, and reduce standard LWE to them for the parameters of interest.