Faster enumeration-based lattice reduction: root Hermite factor \(k^{1/(2k)}\) time \(k^{k/8+o(k)}\)
From MaRDI portal
Publication:2096521
DOI10.1007/978-3-030-56880-1_7zbMath1501.94023OpenAlexW3037078523MaRDI QIDQ2096521
Weiqiang Wen, Shi Bai, Paul Kirchner, Pierre-Alain Fouque, Damien Stehlé, Martin R. Albrecht
Publication date: 9 November 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-56880-1_7
Related Items
Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance, Towards faster polynomial-time lattice reduction, Improving convergence and practicality of slide-type reductions, A lattice reduction algorithm based on sublattice BKZ, On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem, The convergence of slide-type reductions, Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the concrete hardness of learning with errors
- The LLL algorithm. Survey and applications
- On Lovász' lattice reduction and the nearest lattice point problem
- Factoring polynomials with rational coefficients
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Measuring, simulating and exploiting the head concavity phenomenon in BKZ
- Quantum lattice enumeration and tweaking discrete pruning
- Progressive lattice sieving
- Shortest vector from lattice sieving: a few dimensions for free
- Second order statistical behavior of LLL and BKZ
- Estimate all the {LWE, NTRU} schemes!
- Slide reduction, revisited -- filling the gaps in SVP approximation
- The general sieve kernel and new records in lattice reduction
- Revisiting the expected cost of solving uSVP and applications to LWE
- Estimating quantum speedups for lattice sieves
- Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator
- Practical, Predictable Lattice Basis Reduction
- BKZ 2.0: Better Lattice Security Estimates
- Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
- Lattice Enumeration Using Extreme Pruning
- Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
- New directions in nearest neighbor searching with applications to lattice sieving
- Analyzing Blockwise Lattice Algorithms Using Dynamical Systems
- Fast Lattice Point Enumeration with Minimal Overhead
- Predicting Lattice Reduction
