LWE with Side Information: Attacks and Concrete Security Estimation

          @misc{ scivideos_15645,
            doi = {},
            url = {https://simons.berkeley.edu/talks/lwe-side-information-attacks-and-concrete-security-estimation},
            author = {},
            keywords = {},
            language = {en},
            title = {LWE with Side Information: Attacks and Concrete Security Estimation},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {apr},
            note = {15645 see, \url{https://scivideos.org/index.php/Simons-Institute/15645}}
          }
          

Abstract

https://eprint.iacr.org/2020/292 Dana Dachman-Soled and Léo Ducas and Huijing Gong and Mélissa Rossi 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), 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. Category / Keywords: public-key cryptography / LWE, NTRU, Lattice reduction, Cryptanalysis, Side-channels analysis, decryption failures. Date: received 5 Mar 2020, last revised 6 Mar 2020 Contact author: danadach at ece umd edu,l ducas@cwi nl,gong@cs umd edu,melissa rossi@ens fr Available format(s): PDF | BibTeX Citation Version: 20200306:193806 (All versions of this report) Short URL: ia.cr/2020/292