Improving convergence and practicality of slide-type reductions

DOI10.1016/J.IC.2023.105012OpenAlexW4320487262MaRDI QIDQ2687993FDOQ2687993

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

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

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)

Cites Work

• BKZ 2.0: Better lattice security estimates
• A hierarchy of polynomial time lattice basis reduction algorithms
• Public-key cryptosystems from the worst-case shortest vector problem
• On lattices, learning with errors, random linear codes, and cryptography
• Factoring polynomials with rational coefficients
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Trapdoors for hard lattices and new cryptographic constructions
• Title not available (Why is that?)
• Predicting Lattice Reduction
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lattice Point Enumeration on Block Reduced Bases
• Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
• Analyzing blockwise lattice algorithms using dynamical systems
• Finding short lattice vectors within Mordell's inequality
• The shortest vector in a lattice is hard to approximate to within some constant
• Title not available (Why is that?)
• On Positive Definite Quadratic Forms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Practical, Predictable Lattice Basis Reduction
• Observation on the Minimum of a Positive Quadratic Form in Eight Variables
• The general sieve kernel and new records in lattice reduction
• Hardness of approximating the shortest vector problem in lattices
• Measuring, simulating and exploiting the head concavity phenomenon in BKZ
• Approximating the densest sublattice from Rankin's inequality
• Algorithms for the densest sub-lattice problem
• Rankin’s Constant and Blockwise Lattice Reduction
• Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator
• 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
• Symplectic Lattice Reduction and NTRU
• The convergence of slide-type reductions
• Bounding basis reduction properties
• Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance
• Inapproximability of the shortest vector problem: toward a deterministic reduction
• Bounds for Cofactors and Arithmetic Minima of Quadratic Forms

Cited In (6)

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

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)