International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Memory-Efficient BKW Algorithm for Solving the LWE Problem

Authors:
Yu Wei , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS;School of Cyber Security, University of Chinese Academy of Sciences
Lei Bi , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS;School of Cyber Security, University of Chinese Academy of Sciences
Xianhui Lu , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS;School of Cyber Security, University of Chinese Academy of Sciences
Kunpeng Wang , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS;School of Cyber Security, University of Chinese Academy of Sciences
Download:
Search ePrint
Search Google
Conference: PKC 2025
Abstract: The study of attack algorithms for the Learning with Errors (LWE) problem is crucial for the cryptanalysis of LWE-based cryptosystems. The BKW algorithm has gained significant attention as an important combinatorial attack for solving LWE. However, its exponential time and memory requirements severely limit its practical applications, even with medium-sized parameters. In this paper, we present a memory-efficient BKW algorithm for LWE, which extends Bogos's work [Asiacrypt'16] on the Learning Parity with Noise (LPN) problem. While their work improved efficiency, it overlooked the high memory demands of the BKW algorithm. We address this with two key improvements. First, we propose an efficient reduction technique for low-memory regimes, \(c\)-sum-PCS-reduce, which combines the \(c\)-sum technique with Parallel Collision Search (PCS) to achieve a better time-memory trade-off. Second, we present an improved memory-optimized finite automaton for our optimized BKW algorithm by incorporating several efficient memory-saving reduction techniques and pruning potential high-memory paths. Our algorithm, using graphs as a meta tool, can automatically identify the optimal reduction path within the graph, aiming to reduce both time and memory complexities. Compared to the state-of-the-art coded-BKW in the lattice-estimator, our algorithm achieves time complexity improvements ranging from \(2^{3.3}\) to \(2^{26.2}\). Furthermore, memory complexity is improved, with reductions ranging from \(2^{9.7}\) to \(2^{71.3}\).
BibTeX
@inproceedings{pkc-2025-35155,
  title={Memory-Efficient BKW Algorithm for Solving the LWE Problem},
  publisher={Springer-Verlag},
  author={Yu Wei and Lei Bi and Xianhui Lu and Kunpeng Wang},
  year=2025
}