Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms
From MaRDI portal
Nonparametric hypothesis testing (62G10) Learning and adaptive systems in artificial intelligence (68T05) Cryptography (94A60) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Numerical methods for discrete and fast Fourier transforms (65T50) Quantum cryptography (quantum-theoretic aspects) (81P94)
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 that it performs much better than theory predicts and introduce an improvement of it called the pruned FFT distinguisher. Finally, we indicate, via extensive experiments, that the sample dependency due to both LF2 and sample amplification is limited.
Recommendations
Cites work
- scientific article; zbMATH DE number 1024063 (Why is no real title available?)
- An Improved LPN Algorithm
- An improved BKW algorithm for LWE with applications to cryptography and lattices
- Better algorithms for LWE and LWR
- Coded-BKW with sieving
- Coded-BKW: solving LWE using lattice codes
- Dissection-BKW
- Efficient computation of the DFT with only a subset of input or output points
- Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
- Faster algorithms for solving LPN
- How Far Can We Go Beyond Linear Cryptanalysis?
- Improved low-memory subset sum and LPN algorithms via multiple collisions
- LPN decoded
- Lazy modulus switching for the BKW algorithm on LWE
- Making the BKW algorithm practical for LWE
- Never Trust a Bunny
- Noise-tolerant learning, the parity problem, and the statistical query model
- 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 Asymptotics of Solving the LWE Problem Using Coded-BKW With Sieving
- On the asymptotic complexity of solving LWE
- On the complexity of the BKW algorithm on LWE
- On the concrete hardness of learning with errors
- Optimization of \(\mathsf {LPN}\) solving algorithms
- Solving LPN Using Covering Codes
- Solving LPN using covering codes
- The general sieve kernel and new records in lattice reduction
Cited in
(6)- Memory-efficient BKW algorithm for solving the LWE problem
- The informativeness of the gradient revisited
- On the asymptotic complexity of solving LWE
- Making the BKW algorithm practical for LWE
- On the complexity of the BKW algorithm on LWE
- Further improvements of the estimation of key enumeration with applications to solving LWE
This page was built for publication: Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6159444)
