A New Lattice Sieving Algorithm Base on Angular Locality-Sensitive Hashing

摘要

Currently, the space requirement of sieving algorithms to solve the shortest vector problem (SVP) grows as 2~(0.2075n+o(n)), where n is the lattice dimension. In high dimensions, the memory requirement makes them uncompetitive with enumeration algorithms. Shi Bai et al. presents a filtered triple sieving algorithm that breaks the bottleneck with memory 2~(0.1887n+o(n)) and time 2~(0.481n+o(n)). Benefiting from the angular locality-sensitive hashing (LSH) method, our proposed algorithm runs in time 2~(0.4098n+o(n)) with the same space complexity 2~(0.1887n+o(n)) as the filtered triple sieving algorithm. Our experiment demonstrates that the proposed algorithm achieves the desired results. Furthermore, we use the proposed algorithm to solve the closest vector problem (CVP) with the lowest space complexity as far as we know in the literature.