Improved algorithms for the shortest vector problem and the closest vector problem in the infinity norm

DOI10.4230/LIPICS.ISAAC.2018.35MaRDI QIDQ5091027zbMATH OpenFDO

Authors Divesh Aggarwal, Priyanka Mukhopadhyay

Publication date 21 July 2022

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

zbMATH Keywords

latticeclosest vector problemshortest vector problem\(\ell_\infty\) norm

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Sampling methods for shortest vectors, closest vectors and successive minima
• Faster exponential time algorithms for the shortest vector problem
• A sieve algorithm for the shortest lattice vector problem
• A sieve algorithm based on overlattices
• Shortest vector from lattice sieving: a few dimensions for free

Cites work

• scientific article; zbMATH DE number 1852142 (Why is no real title available?)
• A decade of lattice cryptography
• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• A sieve algorithm for the shortest lattice vector problem
• Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
• Covering cubes and the closest vector problem
• Factoring polynomials with rational coefficients
• Finding shortest lattice vectors in the presence of gaps
• Improved low-density subset sum algorithms
• Integer Programming with a Fixed Number of Variables
• Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
• Minkowski's Convex Body Theorem and Integer Programming
• New directions in nearest neighbor searching with applications to lattice sieving
• On Lovász' lattice reduction and the nearest lattice point problem
• On lattices, learning with errors, random linear codes, and cryptography
• Sampling methods for shortest vectors, closest vectors and successive minima
• Sieve algorithms for the shortest vector problem are practical
• Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract)
• Some sieving algorithms for lattice problems

Cited in

(4)

• Approximate CVP\(_p\) in time \(2^{0.802n}\)
• scientific article; zbMATH DE number 634031 (Why is no real title available?)
• On the security of OSIDH
• Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!

This page was built for publication: Improved algorithms for the shortest vector problem and the closest vector problem in the infinity norm

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