
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Faster RotationBased Gauss Sieve for Solving the SVP on General Ideal Lattices
Shintaro NARISADA Hiroki OKADA Kazuhide FUKUSHIMA Shinsaku KIYOMOTO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E104A
No.1
pp.7988 Publication Date: 2021/01/01 Online ISSN: 17451337
DOI: 10.1587/transfun.2020CIP0014 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Keyword: shortest vector problem, Gauss Sieve, ideal lattice, generalization,
Full Text: FreePDF
Summary:
The hardness in solving the shortest vector problem (SVP) is a fundamental assumption for the security of latticebased cryptographic algorithms. In 2010, Micciancio and Voulgaris proposed an algorithm named the Gauss Sieve, which is a fast and heuristic algorithm for solving the SVP. Schneider presented another algorithm named the Ideal Gauss Sieve in 2011, which is applicable to a special class of lattices, called ideal lattices. The Ideal Gauss Sieve speeds up the Gauss Sieve by using some properties of the ideal lattices. However, the algorithm is applicable only if the dimension of the ideal lattice n is a power of two or n+1 is a prime. Ishiguro et al. proposed an extension to the Ideal Gauss Sieve algorithm in 2014, which is applicable only if the prime factor of n is 2 or 3. In this paper, we first generalize the dimensions that can be applied to the ideal lattice properties to when the prime factor of n is derived from 2, p or q for two primes p and q. To the best of our knowledge, no algorithm using ideal lattice properties has been proposed so far with dimensions such as: 20, 44, 80, 84, and 92. Then we present an algorithm that speeds up the Gauss Sieve for these dimensions. Our experiments show that our proposed algorithm is 10 times faster than the original Gauss Sieve in solving an 80dimensional SVP problem. Moreover, we propose a rotationbased Gauss Sieve that is approximately 1.5 times faster than the Ideal Gauss Sieve.


