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

DOI10.1007/978-3-030-56880-1_10MaRDI QIDQ2096526zbMATH OpenOpenAlexFDO

Authors 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

DBKZlattice reductionslide reductionSVP

Mathematics Subject Classification ID

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

Abstract: We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP). As a result, we show the fastest provably correct algorithm for $delta$-approximate SVP for all approximation factors $n^{1/2+varepsilon}leqdeltaleq{n}^{O(1)}$. This is the range of approximation factors most relevant for cryptography.

Recommendations

• Improving convergence and practicality of slide-type reductions
• Slide reduction, successive minima and several~applications
• The convergence of slide-type reductions
• A slack approach to reduced-basis approximation and error estimation for variational inequalities
• Dimensionality reduction of SDPs through sketching
• Sliding Modes in Solving Convex Programming Problems
• Conditional gradient sliding for convex optimization
• scientific article; zbMATH DE number 3856846
• A modified SLP algorithm and its global convergence
• Accelerated gradient sliding for structured convex optimization

Cites work

• A decade of lattice cryptography
• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• A hierarchy of polynomial time lattice basis reduction algorithms
• A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem
• A sieve algorithm for the shortest lattice vector problem
• Analyzing blockwise lattice algorithms using dynamical systems
• Approximating the densest sublattice from Rankin's inequality
• Bounding basis reduction properties
• Computing a lattice basis revisited
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Factoring polynomials with rational coefficients
• Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers
• Finding short lattice vectors within Mordell's inequality
• Finding shortest lattice vectors in the presence of gaps
• scientific article; zbMATH DE number 4213909 (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 1852142 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Lattice reduction: a toolbox for the cryptoanalyst
• New directions in nearest neighbor searching with applications to lattice sieving
• 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
• Sieve algorithms for the shortest vector problem are practical
• Slide reduction, successive minima and several~applications
• Solving the shortest vector problem in 2ⁿ time using discrete Gaussian sampling (extended abstract)
• Symplectic Lattice Reduction and NTRU
• The LLL algorithm. Survey and applications
• Trapdoors for hard lattices and new cryptographic constructions

Cited in

(24)

• 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
• 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
• Dynamic self-dual DeepBKZ lattice reduction with free dimensions and its implementation
• Improving convergence and practicality of slide-type reductions
• A lattice reduction algorithm based on sublattice BKZ
• Slide reduction, successive minima and several~applications
• Subfield attacks on HSVP in ideal lattices
• On module unique-SVP and NTRU
• BS: Blockwise Sieve Algorithm for Finding Short Vectors from Sublattices
• Provable lattice reduction of $$\mathbb {Z}^n$$ with blocksize n/2
• Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
• A complete analysis of the BKZ lattice reduction algorithm
• On the smallest ratio problem of lattice bases
• On the ability to approximate k-DSP of HKZ, BKZ and slide reduction
• Worst-case to average-case hardness of LWE: an alternative perspective
• Improved provable reduction of NTRU and hypercubic lattices
• Solving the shortest vector problem in \(2^{0.63269n+o(n)}\) time on random lattices

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

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