A non-heuristic approach to time-space tradeoffs and optimizations for BKW

DOI10.1007/978-3-031-22969-5_25zbMath1519.94162OpenAlexW3201744628MaRDI QIDQ6135457

Yu Yu, Hanlin Liu

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

zbMATH Keywords

\(c\)-ary tree structuretweaking Wagner's generalized birthday problem

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items (1)

Asymptotics and improvements of sieving for codes

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

This page was built for publication: A non-heuristic approach to time-space tradeoffs and optimizations for BKW