Improving convergence and practicality of slide-type reductions

DOI10.1016/j.ic.2023.105012OpenAlexW4320487262MaRDI QIDQ2687993

Yanyan Li

Publication date: 7 March 2023

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2023.105012

zbMATH Keywords

dynamical systemslattice reductionGaussian heuristicslide reduction

Mathematics Subject Classification ID

Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06)

Uses Software

• BKZ
• fpLLL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A hierarchy of polynomial time lattice basis reduction algorithms
• 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
• The convergence of slide-type reductions
• 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
• Bounding basis reduction properties
• The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
• Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator
• Practical, Predictable Lattice Basis Reduction
• Approximating the densest sublattice from Rankin’s inequality
• Lattice Point Enumeration on Block Reduced Bases
• BKZ 2.0: Better Lattice Security Estimates
• Hardness of approximating the shortest vector problem in lattices
• Trapdoors for hard lattices and new cryptographic constructions
• Symplectic Lattice Reduction and NTRU
• Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
• Bounds for Cofactors and Arithmetic Minima of Quadratic Forms
• Public-key cryptosystems from the worst-case shortest vector problem
• Analyzing Blockwise Lattice Algorithms Using Dynamical Systems
• Predicting Lattice Reduction
• Algorithms for the Densest Sub-Lattice Problem
• Rankin’s Constant and Blockwise Lattice Reduction
• On Positive Definite Quadratic Forms
• Observation on the Minimum of a Positive Quadratic Form in Eight Variables
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: Improving convergence and practicality of slide-type reductions