Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem

Abstract

In this paper, we present an improvement of the Nguyen-Vidick heuristic sieve algorithm for shortest vector problem in general lattices, which time complexity is 20.3836n polynomial computations, and space complexity is 20.2557n. In the new algorithm, we introduce a new sieve technique with two-level instead of the previous one-level sieve, and complete the complexity estimation by calculating the irregular spherical cap covering.