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

DOI10.4230/LIPICS.ISAAC.2018.35MaRDI QIDQ5091027FDOQ5091027

Authors: Divesh Aggarwal, Priyanka Mukhopadhyay 

Publication date: 21 July 2022

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

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

Cited In (4)

• On the security of OSIDH
• Title not available (Why is that?)
• Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
• Approximate CVP\(_p\) in time \(2^{0.802n}\)

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)