Open AccessThe faster lattice sieving for SVP
Author(s) -
Huibing Song,
Changzhi Gu,
Zheng Yan
Publication year - 2019
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1324/1/012008
Subject(s) - lattice problem , lattice (music) , speedup , lattice based cryptography , lattice reduction , algorithm , sieve (category theory) , computer science , mathematics , combinatorics , cryptography , parallel computing , physics , statistics , beamforming , quantum cryptography , quantum mechanics , mimo , acoustics , quantum information , quantum
The security of lattice-based cryptography is based on the hardness of the difficult problems on lattice, especially the famous shortest vector problem. There are many famous heuristic lattice sieving algorithms to solve SVP, such as the Gauss Sieve, NV Sieve, which deal the full-rank n -dimensional lattice from start. Inspired by the idea of rank reduction, in this paper we present new technique on lattice sieving to make the algorithm solve the SVP faster. We split the basis of “bigger” lattice into several blocks according to some rule until the sublattice is small enough. Then we recursively sieved on these sub-lattices to get short vector lists. With the short vector lists, we can find the shortest vector when the algorithm recoverd the original lattice. This lead to obviously speedup with the recursive procedure without extra space overhead. Compared with the Gauss Sieve, the new method converge faster, and achieved at least 70% acceleration.