Improving convergence and practicality of slide-type reductions

DOI10.1016/J.IC.2023.105012MaRDI QIDQ2687993zbMATH OpenOpenAlexFDO

Authors 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) Lattices and convex bodies (number-theoretic aspects) (11H06) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• The convergence of slide-type reductions
• Slide reduction, revisited -- filling the gaps in SVP approximation
• Slide reduction, successive minima and several~applications
• Practical, Predictable Lattice Basis Reduction
• Analyzing blockwise lattice algorithms using dynamical systems

Cites work

• scientific article; zbMATH DE number 1676629 (Why is no real title available?)
• scientific article; zbMATH DE number 5485482 (Why is no real title available?)
• scientific article; zbMATH DE number 3980484 (Why is no real title available?)
• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• scientific article; zbMATH DE number 1335879 (Why is no real title available?)
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• A hierarchy of polynomial time lattice basis reduction algorithms
• Algorithms for the densest sub-lattice problem
• Analyzing blockwise lattice algorithms using dynamical systems
• Approximating the densest sublattice from Rankin's inequality
• BKZ 2.0: Better lattice security estimates
• Bounding basis reduction properties
• Bounds for Cofactors and Arithmetic Minima of Quadratic Forms
• Factoring polynomials with rational coefficients
• Faster enumeration-based lattice reduction: root Hermite factor \(k^{1/(2k)}\) time \(k^{k/8+o(k)}\)
• Finding short lattice vectors within Mordell's inequality
• Hardness of approximating the shortest vector problem in lattices
• Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
• Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator
• Inapproximability of the shortest vector problem: toward a deterministic reduction
• Lattice Point Enumeration on Block Reduced Bases
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance
• Measuring, simulating and exploiting the head concavity phenomenon in BKZ
• Observation on the Minimum of a Positive Quadratic Form in Eight Variables
• On Positive Definite Quadratic Forms
• On lattices, learning with errors, random linear codes, and cryptography
• Practical, Predictable Lattice Basis Reduction
• Predicting Lattice Reduction
• Public-key cryptosystems from the worst-case shortest vector problem
• Rankin’s Constant and Blockwise Lattice Reduction
• Slide reduction, revisited -- filling the gaps in SVP approximation
• Symplectic Lattice Reduction and NTRU
• The convergence of slide-type reductions
• The general sieve kernel and new records in lattice reduction
• The shortest vector in a lattice is hard to approximate to within some constant
• Trapdoors for hard lattices and new cryptographic constructions

Cited in

(6)

• Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP
• Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes
• The convergence of slide-type reductions
• Slide reduction, revisited -- filling the gaps in SVP approximation
• Slide reduction, successive minima and several~applications
• A complete analysis of the BKZ lattice reduction algorithm

Describes a project that uses

Uses Software

• BKZ
• fpLLL

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2687993)