Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in norm
arXiv:1907.04406 · doi:10.3390/a14120362
Abstract
In this work, we give provable sieving algorithms for the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) on lattices in norm (). The running time we obtain is better than existing provable sieving algorithms. We give a new linear sieving procedure that works for all norm (). 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 , which is much less than the 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 norm, where we achieve a time complexity of , while the List Sieve Birthday algorithm has a running time of . We adopt our sieving techniques to approximation algorithms for SVP and CVP in norm () and show that our algorithm has a running time of , while previous algorithms have a time complexity of .
arXiv commentV3 : New diagrams and explanations. arXiv admin note: text overlap with arXiv:1801.02358
References in corpus (7)
- Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
- Solving the Shortest Vector Problem in Time via Discrete Gaussian Sampling
- Classical Hardness of Learning with Errors
- Near-Optimal Deterministic Algorithms for Volume Computation and Lattice Problems via M-Ellipsoids
- (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 -Time Algorithm for SVP (and CVP)