An Improved BKW Algorithm for LWE with Applications to Cryptography and\n Lattices

2015/06/08 by Paul Kirchner, Kirchner, Paul, Pierre-Alain Fouque +1
Computer Science · #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #I.1.2 #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.1506.02717

openalex publication_date 2015/06/08 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28

Abstract

In this paper, we study the Learning With Errors problem and its binary\nvariant, where secrets and errors are binary or taken in a small interval. We\nintroduce a new variant of the Blum, Kalai and Wasserman algorithm, relying on\na quantization step that generalizes and fine-tunes modulus switching. In\ngeneral this new technique yields a significant gain in the constant in front\nof the exponent in the overall complexity. We illustrate this by solving p\nwithin half a day a LWE instance with dimension n = 128, modulus q = n²,\nGaussian noise \α = 1/(\√(n/\π) \log² n) and binary secret, using\n2²⁸ samples, while the previous best result based on BKW claims a time\ncomplexity of 2⁷⁴ with 2⁶⁰ samples for the same parameters. We then\nintroduce variants of BDD, GapSVP and UniqueSVP, where the target point is\nrequired to lie in the fundamental parallelepiped, and show how the previous\nalgorithm is able to solve these variants in subexponential time. Moreover, we\nalso show how the previous algorithm can be used to solve the BinaryLWE problem\nwith n samples in subexponential time 2^{(\ln 2/2+o(1))n/\log \log n}. This\nanalysis does not require any heuristic assumption, contrary to other algebraic\napproaches; instead, it uses a variant of an idea by Lyubashevsky to generate\nmany samples from a small number of samples. This makes it possible to\nasymptotically and heuristically break the NTRU cryptosystem in subexponential\ntime (without contradicting its security assumption). We are also able to solve\nsubset sum problems in subexponential time for density o(1), which is of\nindependent interest: for such density, the previous best algorithm requires\nexponential time. As a direct application, we can solve in subexponential time\nthe parameters of a cryptosystem based on this problem proposed at TCC 2010.\n

Related

• On the Sample Complexity of solving LWE using BKW-Style Algorithms
• The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors
• Wagner's Algorithm Provably Runs in Subexponential Time for SIS^∞
• Classical Hardness of Learning with Errors
• A reduction from LWE problem to dihedral coset problem