Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ${\ell }_p$ norm

Abstract

In this work, we give provable sieving algorithms for the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) on lattices in ${\ell }_p$ norm ($1\le p\le \infty$). The running time we obtain is better than existing provable sieving algorithms. We give a new linear sieving procedure that works for all ${\ell }_p$ norm ($1\le p\le \infty$). The main idea is to divide the space into hypercubes such that each vector can be mapped efficiently to a sub-region. We achieve a time complexity of $2^{2.751n+o(n)}$, which is much less than the $2^{3.849n+o(n)}$ complexity of the previous best algorithm. We also introduce a mixed sieving procedure, where a point is mapped to a hypercube within a ball and then a quadratic sieve is performed within each hypercube. This improves the running time, especially in the ${\ell }_2$ norm, where we achieve a time complexity of $2^{2.25n+o(n)}$, while the List Sieve Birthday algorithm has a running time of $2^{2.465n+o(n)}$. We adopt our sieving techniques to approximation algorithms for SVP and CVP in ${\ell }_p$ norm ($1\le p\le \infty$) and show that our algorithm has a running time of $2^{2.001n+o(n)}$, while previous algorithms have a time complexity of $2^{3.169n+o(n)}$.

V3 : New diagrams and explanations. arXiv admin note: text overlap with arXiv:1801.02358

References in corpus (4)

• Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
• (Gap/S)ETH Hardness of SVP
• The Projection Games Conjecture and the Hardness of Approximation of super-SAT and related problems
• Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)