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.

Cryptanalysis, Decryption failures, Lattice reduction, LWE, NTRU, Side-channels analysis
doi.org/10.1007/978-3-030-56880-1_12
Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence
40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020
Centrum Wiskunde & Informatica, Amsterdam, The Netherlands

Dachman-Soled, D, Ducas, L, Gong, H, & Rossi, M. (2020). LWE with side information: Attacks and concrete security estimation. In Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence. doi:10.1007/978-3-030-56880-1_12