## CryptoDB

### Paper: LWE with Side Information: Attacks and Concrete Security Estimation

Authors: Dana Dachman-Soled , University of Maryland, College Park Léo Ducas , CWI Amsterdam Huijing Gong , University of Maryland, College Park Mélissa Rossi , ANSSI | ENS Paris DOI: http://dx.doi.org/10.1007/978-3-030-56880-1_12 (login may be required) Search ePrint Search Google CRYPTO 2020 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), that were previously not known to (slightly) benefit from lattice attacks. 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). Contrary to ad-hoc practical attacks exploiting side-channel leakage, our work is a generic way to estimate security loss even given very little side-channel information.
##### BibTeX
@inproceedings{crypto-2020-30436,
title={LWE with Side Information: Attacks and Concrete Security Estimation},
publisher={Springer-Verlag},
doi={http://dx.doi.org/10.1007/978-3-030-56880-1_12},
author={Dana Dachman-Soled and Léo Ducas and Huijing Gong and Mélissa Rossi},
year=2020
}