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

Dana Dachman-Soled, Huijing Gong, 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$.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
public-key cryptographylattice-based cryptographyleakage resilienceRing-LWE
Contact author(s)
ariash @ umd edu
History
Short URL
https://ia.cr/2018/1068

CC BY

BibTeX

@misc{cryptoeprint:2018/1068,
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{https://eprint.iacr.org/2018/1068}},
url = {https://eprint.iacr.org/2018/1068}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.