[DDRG20] LWE with Side Information: Attacks and Concrete Security Estimation

Authors: Dana Dachman-Soled, Léo Ducas, Huijing Gong, Mélissa Rossi | Venue: CRYPTO 2020 | Source

Abstract

We propose a framework for cryptanalysis of LWE-based schemes when the attacker has access to side information — beyond the public data — that may arise from decryption failures, side channels, or implementation leakage. The side information is modeled as “hints”: noisy inner products $⟨{\mathbf{v}}_i,\mathbf{s}⟩+e_i^{\prime }$ for known vectors ${\mathbf{v}}_i$, which the attacker can progressively incorporate before running lattice reduction. Our toolkit includes operations for sparsifying the lattice, projecting onto hint-defined hyperplanes, and intersecting with them. We apply the framework to provide concrete security estimates for LAC, Round5, and NTRU under realistic leakage scenarios, and release the leaky-LWE-Estimator for the community.

BibTeX

Copy

@Inproceedings{C:DDGR20,
  author = {Dana {Dachman-Soled} and L{\'e}o Ducas and Huijing Gong and M{\'e}lissa Rossi},
  title = {{LWE} with Side Information: Attacks and Concrete Security Estimation},
  pages = {329--358},
  editor = {Daniele Micciancio and Thomas Ristenpart},
  booktitle = {Advances in Cryptology -- {CRYPTO}~2020, Part~II},
  volume = {12171},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~17--21},
  publisher = {Springer, Cham, Switzerland},
  year = {2020},
  doi = {10.1007/978-3-030-56880-1_12},
}