Modeling and Simulating the Sample Complexity of solving LWE using BKW-Style Algorithms

Qian Guo; Erik Mårtensson; Paul Stankovski Wagner

Paper 2022/988

Modeling and Simulating the Sample Complexity of solving LWE using BKW-Style Algorithms

Qian Guo

, Lund University

Erik Mårtensson

, University of Bergen, Lund University

Paul Stankovski Wagner

, Lund University

Abstract

The Learning with Errors (LWE) problem receives much attention in cryptography, mainly due to its fundamental significance in post-quantum cryptography. Among its solving algorithms, the Blum-Kalai-Wasserman (BKW) algorithm, originally proposed for solving the Learning Parity with Noise (LPN) problem, performs well, especially for certain parameter settings with cryptographic importance. The BKW algorithm consists of two phases, the reduction phase and the solving phase. In this work, we study the performance of distinguishers used in the solving phase. We show that the Fast Fourier Transform (FFT) distinguisher from Eurocrypt’15 has the same sample complexity as the optimal distinguisher, when making the same number of hypotheses. We also show via simulation that it performs much better than previous theory predicts and develop a sample complexity model that matches the simulations better. We also introduce an improved, pruned version of the FFT distinguisher. Finally, we indicate, via extensive experiments, that the sample dependency due to both LF2 and sample amplification is limited.

Note: The paper is accepted for publication at Cryptography and Communications (CCDS) and the version of record will soon be accessible using the provided DOI. A conference version of the paper was published at ISIT 2021.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. Cryptography and Communications (CCDS)
Keywords: LWE BKW FFT distinguisher Hypothesis testing
Contact author(s): qian guo @ eit lth se
erik martensson @ uib no
paul stankovski_wagner @ eit lth se
History: 2022-08-03: approved; 2022-08-02: received; See all versions
Short URL: https://ia.cr/2022/988
License: CC BY

BibTeX

@misc{cryptoeprint:2022/988,
      author = {Qian Guo and Erik Mårtensson and Paul Stankovski Wagner},
      title = {Modeling and Simulating the Sample Complexity of solving LWE using BKW-Style Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2022/988},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/988}},
      url = {https://eprint.iacr.org/2022/988}
}