Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms
DOI10.1007/s12095-022-00597-0zbMath1516.94033arXiv2102.02126OpenAlexW4292454253WikidataQ114849085 ScholiaQ114849085MaRDI QIDQ6159444
Paul Stankovski Wagner, Erik Mårtensson, Qian Guo
Publication date: 20 June 2023
Published in: Cryptography and Communications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2102.02126
Nonparametric hypothesis testing (62G10) Learning and adaptive systems in artificial intelligence (68T05) Cryptography (94A60) Numerical methods for discrete and fast Fourier transforms (65T50) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Quantum cryptography (quantum-theoretic aspects) (81P94)
Cites Work
- Unnamed Item
- On solving LPN using BKW and variants, Implementation and analysis
- On the concrete hardness of learning with errors
- LPN decoded
- On the asymptotic complexity of solving LWE
- Dissection-BKW
- Making the BKW algorithm practical for LWE
- Improved low-memory subset sum and LPN algorithms via multiple collisions
- On the complexity of the BKW algorithm on LWE
- The general sieve kernel and new records in lattice reduction
- Solving LPN using covering codes
- Coded-BKW with sieving
- Faster Algorithms for Solving LPN
- Never Trust a Bunny
- Solving LPN Using Covering Codes
- Better Algorithms for LWE and LWR
- Optimization of $$\mathsf {LPN}$$ Solving Algorithms
- Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
- Coded-BKW: Solving LWE Using Lattice Codes
- An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
- An Improved LPN Algorithm
- Efficient computation of the DFT with only a subset of input or output points
- On the Asymptotics of Solving the LWE Problem Using Coded-BKW With Sieving
- Lazy Modulus Switching for the BKW Algorithm on LWE
- How Far Can We Go Beyond Linear Cryptanalysis?
- 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
