A non-heuristic approach to time-space tradeoffs and optimizations for BKW
From MaRDI portal
Publication:6135457
DOI10.1007/978-3-031-22969-5_25zbMath1519.94162OpenAlexW3201744628MaRDI QIDQ6135457
Publication date: 25 August 2023
Published in: Advances in Cryptology – ASIACRYPT 2022 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-031-22969-5_25
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On solving LPN using BKW and variants, Implementation and analysis
- The extended \(k\)-tree algorithm
- Two moments suffice for Poisson approximations: The Chen-Stein method
- Progressive lattice sieving
- Shortest vector from lattice sieving: a few dimensions for free
- LPN decoded
- On iterative collision search for LPN and subset sum
- On the asymptotic complexity of solving LWE
- Speed-ups and time-memory trade-offs for tuple lattice sieving
- Dissection-BKW
- An algorithmic framework for the generalized birthday problem
- 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
- Solving LPN using covering codes
- Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
- Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing
- Optimization of $$\mathsf {LPN}$$ Solving Algorithms
- Tuple lattice sieving
- Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
- An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
- An Improved LPN Algorithm
- Parallel and Concurrent Security of the HB and HB + Protocols
- Cryptography with Constant Input Locality
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- On the Asymptotics of Solving the LWE Problem Using Coded-BKW With Sieving
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Improved Algorithms for the Approximate k-List Problem in Euclidean Norm
- Noise-tolerant learning, the parity problem, and the statistical query model
- On lattices, learning with errors, random linear codes, and cryptography
