Paper 2018/1068

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

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


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$.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
public-key cryptographylattice-based cryptographyleakage resilienceRing-LWE
Contact author(s)
ariash @ umd edu
2018-11-09: received
Short URL
Creative Commons Attribution


      author = {Dana Dachman-Soled and Huijing Gong and Mukul Kulkarni and Aria Shahverdi},
      title = {Partial Key Exposure in Ring-LWE-Based Cryptosystems: Attacks and Resilience},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1068},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.