Paper 2020/292
LWE with Side Information: Attacks and Concrete Security Estimation
Abstract
We propose a framework for cryptanalysis of lattice-based schemes, when side information---in the form of ``hints''--- about the secret and/or error is available. Our framework generalizes the so-called primal lattice reduction attack, and allows the progressive integration of hints before running a final lattice reduction step. Our techniques for integrating hints include sparsifying the lattice, projecting onto and intersecting with hyperplanes, and/or altering the distribution of the secret vector. Our main contribution is to propose a toolbox and a methodology to integrate such hints into lattice reduction attacks and to predict the performance of those lattice attacks with side information. While initially designed for side-channel information, our framework can also be used in other cases: exploiting decryption failures, or simply exploiting constraints imposed by certain schemes (LAC, Round5, NTRU). We implement a Sage 9.0 toolkit to actually mount such attacks with hints when computationally feasible, and to predict their performances on larger instances. We provide several end-to-end application examples, such as an improvement of a single trace attack on Frodo by Bos et al (SAC 2018). In particular, our work can estimates security loss even given very little side information, leading to a smooth measurement/computation trade-off for side-channel attacks.
Note: Revision note: - adding a discussion about extreme hints
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in CRYPTO 2020
- Keywords
- LWE NTRU Lattice reduction Cryptanalysis Side-channels analysis decryption failures.
- Contact author(s)
-
danadach @ ece umd edu
gong @ cs umd edu
melissa rossi @ ens fr - History
- 2022-10-24: last of 3 revisions
- 2020-03-06: received
- See all versions
- Short URL
- https://ia.cr/2020/292
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/292,
author = {Dana Dachman-Soled and Léo Ducas and Huijing Gong and Mélissa Rossi},
title = {LWE with Side Information: Attacks and Concrete Security Estimation},
howpublished = {Cryptology ePrint Archive, Paper 2020/292},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/292}},
url = {https://eprint.iacr.org/2020/292}
}
