Memory-efficient BKW algorithm for solving the LWE problem

DOI10.1007/978-3-031-91823-0_11MaRDI QIDQ6951441zbMATH OpenFDO

Authors Yu Wei, Lei Bi, Xianhui Lu, Kun Peng Wang

Publication date 29 July 2025

Full work available at URL https://doi.org/10.1007/978-3-031-91823-0_11

zbMATH Keywords

learning with errors problempost-quantum cryptanalysisthe BKW algorithmtime-memory trade-off

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Cites work

• A new algorithm for the unbalanced meet-in-the-middle problem
• A non-heuristic approach to time-space tradeoffs and optimizations for BKW
• An improved BKW algorithm for LWE with applications to cryptography and lattices
• An Improved LPN Algorithm
• Better algorithms for LWE and LWR
• Better key sizes (and attacks) for LWE-based encryption
• BKZ 2.0: Better lattice security estimates
• Coded-BKW with sieving
• Coded-BKW: solving LWE using lattice codes
• Dissection-BKW
• Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
• Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
• Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS
• Improved low-memory subset sum and LPN algorithms via multiple collisions
• IX. On the problem of the most efficient tests of statistical hypotheses
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Lattice-based Cryptography
• Lazy modulus switching for the BKW algorithm on LWE
• Meet-in-the-middle attacks revisited: key-recovery, collision, and preimage attacks
• Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms
• Multi-user collisions: applications to discrete logarithm, Even-Mansour and PRINCE
• New Algorithms for Learning in Presence of Errors
• Noise-tolerant learning, the parity problem, and the statistical query model
• On lattices, learning with errors, random linear codes, and cryptography
• On solving LPN using BKW and variants, Implementation and analysis
• On the asymptotic complexity of solving LWE
• On the Asymptotics of Solving the LWE Problem Using Coded-BKW With Sieving
• On the complexity of the BKW algorithm on LWE
• Optimization of \(\mathsf {LPN}\) solving algorithms
• Parallel collision search with cryptanalytic applications
• Solving BDD by enumeration: an update
• Solving LPN Using Covering Codes
• Topological quantum Markov processes

This page was built for publication: Memory-efficient BKW algorithm for solving the LWE problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6951441)