Faster Rotation-Based Gauss Sieve for Solving the SVP on General Ideal Lattices

Shintaro NARISADA; Hiroki OKADA; Kazuhide FUKUSHIMA; Shinsaku KIYOMOTO

doi:10.1587/transfun.2020CIP0014

Open Access
Faster Rotation-Based Gauss Sieve for Solving the SVP on General Ideal Lattices

Shintaro NARISADA, Hiroki OKADA, Kazuhide FUKUSHIMA, Shinsaku KIYOMOTO

Full Text Views

136

Cite this

Free PDF (1.4MB)

Summary :

The hardness in solving the shortest vector problem (SVP) is a fundamental assumption for the security of lattice-based 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 80-dimensional SVP problem. Moreover, we propose a rotation-based Gauss Sieve that is approximately 1.5 times faster than the Ideal Gauss Sieve.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.1 pp.79-88

Publication Date: 2021/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.2020CIP0014

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category

Authors

Shintaro NARISADA
  KDDI Research, Inc.
Hiroki OKADA
  KDDI Research, Inc.
Kazuhide FUKUSHIMA
  KDDI Research, Inc.
Shinsaku KIYOMOTO
  KDDI Research, Inc.

Keyword

shortest vector problem, Gauss Sieve, ideal lattice, generalization

Cite this

Copy

Shintaro NARISADA, Hiroki OKADA, Kazuhide FUKUSHIMA, Shinsaku KIYOMOTO, "Faster Rotation-Based Gauss Sieve for Solving the SVP on General Ideal Lattices" in IEICE TRANSACTIONS on Fundamentals, vol. E104-A, no. 1, pp. 79-88, January 2021, doi: 10.1587/transfun.2020CIP0014.
Abstract: The hardness in solving the shortest vector problem (SVP) is a fundamental assumption for the security of lattice-based 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 80-dimensional SVP problem. Moreover, we propose a rotation-based Gauss Sieve that is approximately 1.5 times faster than the Ideal Gauss Sieve.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020CIP0014/_p

Copy

@ARTICLE{e104-a_1_79,
author={Shintaro NARISADA, Hiroki OKADA, Kazuhide FUKUSHIMA, Shinsaku KIYOMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Faster Rotation-Based Gauss Sieve for Solving the SVP on General Ideal Lattices},
year={2021},
volume={E104-A},
number={1},
pages={79-88},
abstract={The hardness in solving the shortest vector problem (SVP) is a fundamental assumption for the security of lattice-based 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 80-dimensional SVP problem. Moreover, we propose a rotation-based Gauss Sieve that is approximately 1.5 times faster than the Ideal Gauss Sieve.},
keywords={},
doi={10.1587/transfun.2020CIP0014},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Faster Rotation-Based Gauss Sieve for Solving the SVP on General Ideal Lattices
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 79
EP - 88
AU - Shintaro NARISADA
AU - Hiroki OKADA
AU - Kazuhide FUKUSHIMA
AU - Shinsaku KIYOMOTO
PY - 2021
DO - 10.1587/transfun.2020CIP0014
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E104-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2021
AB - The hardness in solving the shortest vector problem (SVP) is a fundamental assumption for the security of lattice-based 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 80-dimensional SVP problem. Moreover, we propose a rotation-based Gauss Sieve that is approximately 1.5 times faster than the Ideal Gauss Sieve.
ER -