Slide reduction, revisited -- filling the gaps in SVP approximation

DOI10.1007/978-3-030-56880-1_10zbMath1504.94089arXiv1908.03724OpenAlexW3080869780MaRDI QIDQ2096526

Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, Noah Stephens-Davidowitz

Publication date: 9 November 2022

Full work available at URL: https://arxiv.org/abs/1908.03724

zbMATH Keywords

lattice reductionSVPDBKZslide reduction

Mathematics Subject Classification ID

Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Approximation algorithms (68W25)

Related Items

Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ Towards faster polynomial-time lattice reduction ⋮ Property-preserving hash functions for Hamming distance from standard assumptions ⋮ Subfield attacks on HSVP in ideal lattices ⋮ On module unique-SVP and NTRU ⋮ Improving convergence and practicality of slide-type reductions ⋮ A lattice reduction algorithm based on sublattice BKZ ⋮ Dynamic self-dual DeepBKZ lattice reduction with free dimensions and its implementation ⋮ A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP ⋮ Advanced lattice sieving on GPUs, with tensor cores ⋮ The convergence of slide-type reductions ⋮ On the success probability of solving unique SVP via BKZ ⋮ Faster enumeration-based lattice reduction: root Hermite factor \(k^{1/(2k)}\) time \(k^{k/8+o(k)}\) ⋮ Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The LLL algorithm. Survey and applications
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Lattice reduction: a toolbox for the cryptoanalyst
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Bounding basis reduction properties
• Finding Shortest Lattice Vectors in the Presence of Gaps
• A Decade of Lattice Cryptography
• Practical, Predictable Lattice Basis Reduction
• A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
• SLIDE REDUCTION, SUCCESSIVE MINIMA AND SEVERAL APPLICATIONS
• Approximating the densest sublattice from Rankin’s inequality
• Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers
• Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
• Integer Programming with a Fixed Number of Variables
• A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem
• Sieve algorithms for the shortest vector problem are practical
• Trapdoors for hard lattices and new cryptographic constructions
• Symplectic Lattice Reduction and NTRU
• New directions in nearest neighbor searching with applications to lattice sieving
• Computing a Lattice Basis Revisited
• Public-key cryptosystems from the worst-case shortest vector problem
• A sieve algorithm for the shortest lattice vector problem
• Analyzing Blockwise Lattice Algorithms Using Dynamical Systems
• Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)
• Predicting Lattice Reduction
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Rankin’s Constant and Blockwise Lattice Reduction
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: Slide reduction, revisited -- filling the gaps in SVP approximation