You are looking at a specific version 20110828:131448 of this paper.
See the latest version.
Paper 2010/647
Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector Problem
Xiaoyun Wang and Mingjie Liu and Chengliang Tian and Jingguo Bi
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 2^0.3836n polynomial computations, and space complexity is 2^0.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.
Metadata
- Available format(s)
- Publication info
- Published elsewhere. Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security (ASIACCS 2011)
- Keywords
- latticeshortest vectorsieveheuristicsphere covering
- Contact author(s)
- xiaoyunwang at mail tsinghua edu cn,liu-mj07 @ mails tsinghua edu cn
- History
- 2011-08-28: last of 3 revisions
- 2010-12-21: received
- See all versions
- Short URL
- https://ia.cr/2010/647
- License
-
CC BY