A complete analysis of the BKZ lattice reduction algorithm

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Authentication, digital signatures and secret sharing (94A62) Quadratic forms (reduction theory, extreme forms, etc.) (11H55)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Projection matrices, generalized inverse matrices, and singular value decomposition.
A modification of the LLL reduction algorithm
A hierarchy of polynomial time lattice basis reduction algorithms
The incomplete beta function - a historical profile
A new principle in the geometry of numbers, with some applications.
Lower bounds on lattice enumeration with extreme pruning
Advanced lattice sieving on GPUs, with tensor cores
Faster enumeration-based lattice reduction: root Hermite factor \(k^{1/(2k)}\) time \(k^{k/8+o(k)}\)
Slide reduction, revisited -- filling the gaps in SVP approximation
Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance
The general sieve kernel and new records in lattice reduction
Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes
Bounding basis reduction properties
A mean value theorem in geometry of numbers
Improving convergence and practicality of slide-type reductions
Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator
Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
Faster LLL-type Reduction of Lattice Bases
BKZ 2.0: Better Lattice Security Estimates
Lattice Enumeration Using Extreme Pruning
Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
Bounds for Cofactors and Arithmetic Minima of Quadratic Forms
On the KZ Reduction
Computing a Lattice Basis Revisited
A sieve algorithm for the shortest lattice vector problem
Analyzing Blockwise Lattice Algorithms Using Dynamical Systems
Predicting Lattice Reduction
Random Sampling Revisited: Lattice Enumeration with Discrete Pruning
Rankin’s Constant and Blockwise Lattice Reduction
Observation on the Minimum of a Positive Quadratic Form in Eight Variables

This page was built for publication: A complete analysis of the BKZ lattice reduction algorithm