Cryptology ePrint Archive: Report 2018/1068

Partial Key Exposure in Ring-LWE-Based Cryptosystems: Attacks and Resilience

Dana Dachman-Soled and Huijing Gong and Mukul Kulkarni and Aria Shahverdi

Abstract: We initiate the study of partial key exposure in ring-LWE-based cryptosystems. Specifically, we

- Introduce the search and decision Leaky-RLWE assumptions (Leaky-SRLWE, Leaky-DRLWE), to formalize the hardness of search/decision RLWE under leakage of some fraction of coordinates of the NTT transform of the RLWE secret and/or error.

- Present and implement an efficient key exposure attack that, given certain $1/4$-fraction of the coordinates of the NTT transform of the RLWE secret, along with RLWE instances, recovers the full RLWE secret for standard parameter settings.

- Present a search-to-decision reduction for Leaky-RLWE for certain types of key exposure.

- Analyze the security of NewHope key exchange under partial key exposure of $1/8$-fraction of the secrets and error.

We show that, assuming that Leaky-DRLWE is hard for these parameters, the shared key $v$ (which is then hashed using a random oracle) is computationally indistinguishable from a random variable with average min-entropy $238$, conditioned on transcript and leakage, whereas without leakage the min-entropy is $256$.

Category / Keywords: public-key cryptography / public-key cryptography, lattice-based cryptography, leakage resilience, Ring-LWE