Crypto Seminar - Zeyu Liu April 21, 2025 2:00pm — 3:00pm Location: In Person and Virtual - ET - Mehrabian Collaborative Innovation Center 1313 (Special Time / Location) Speaker: ZEYU LIU , Ph.D. Student, Applied Cryptography Laboratory, Computer Science Department, Yale University https://zeyuthomasliu.github.io/ Snake-eye Resistant PKE from LWE for Oblivious Message Retrieval and Robust Encryption In this work, we introduce snake-eye resistance, a new security property for public-key encryption (PKE). This property ensures that a ciphertext—potentially adversarially generated—cannot decrypt to the same plaintext under two different secret keys. Snake-eye resistance is particularly useful for (1) preventing spamming attacks in oblivious message retrieval (OMR) and (2) enabling efficient robust encryption schemes. We first analyze the snake-eye resistance of lattice-based PKE schemes. Our study reveals that while Regev05 and PVW08 satisfy this property, more efficient, state-of-the-art schemes like Crystals-Kyber do not. To bridge this gap, we propose LWEmongrass, a new lattice-based PKE scheme that is provably snake-eye resistant under the standard LWE assumption while significantly improving efficiency over Regev05 and PVW08. Applying LWEmongrass to OMR, we achieve a 12× speedup over existing spamming-attack-resistant OMR schemes (conjectured in LT22 and proven in this work), while maintaining provable security under the LWE assumption. Additionally, we establish that snake-eye resistance implies robustness, yielding the first robust lattice-based PKE scheme that avoids the inefficiencies of the KEM-DEM paradigm. As a contribution of independent interest, we introduce two LWE variants with side information, which serve as key building blocks in our security proofs and enable reductions from standard LWE for relevant parameter settings. Event Website: https://sites.google.com/view/crypto-seminar/home Add event to Google Add event to iCal
