×

A new lattice sieving algorithm base on angular locality-sensitive hashing. (English) Zbl 1426.94131

Chen, Xiaofeng (ed.) et al., Information security and cryptology. 13th international conference, Inscrypt 2017, Xi’an, China, November 3–5, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10726, 65-80 (2018).
Summary: 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. [S. Bai et al. [LMS J. Comput. Math. 19A, Spec. Iss., 146–162 (2016; Zbl 1404.11140)] presented 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.
For the entire collection see [Zbl 1387.94003].

MSC:

94A60 Cryptography
11Y16 Number-theoretic algorithms; complexity

Citations:

Zbl 1404.11140
PDFBibTeX XMLCite
Full Text: DOI