Paper 2013/388

Parallel Gauss Sieve Algorithm : Solving the SVP in the Ideal Lattice of 128-dimensions

Tsukasa Ishiguro, Shinsaku Kiyomoto, Yutaka Miyake, and Tsuyoshi Takagi

Abstract

In this paper, we report that we have solved the SVP Challenge over a 128-dimensional lattice in Ideal Lattice Challenge from TU Darmstadt, which is currently the highest dimension in the challenge that has ever been solved. The security of lattice-based cryptography is based on the hardness of solving the shortest vector problem (SVP) in lattices. In 2010, Micciancio and Voulgaris proposed a Gauss Sieve algorithm for heuristically solving the SVP using a list $L$ of Gauss-reduced vectors. Milde and Schneider proposed a parallel implementation method for the Gauss Sieve algorithm. However, the efficiency of the more than 10 threads in their implementation decreased due to the large number of non-Gauss-reduced vectors appearing in the distributed list of each thread. In this paper, we propose a more practical parallelized Gauss Sieve algorithm. Our algorithm deploys an additional Gauss-reduced list $V$ of sample vectors assigned to each thread, and all vectors in list $L$ remain Gauss-reduced by mutually reducing them using all sample vectors in $V$. Therefore, our algorithm allows the Gauss Sieve algorithm to run for large dimensions with a small communication overhead. Finally, we succeeded in solving the SVP Challenge over a 128-dimensional ideal lattice generated by the cyclotomic polynomial $x^{128}+1$ using about 30,000 CPU hours.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown status
Keywords
shortest vector problemlattice-based cryptographyideal latticeGauss Sieve algorithmparallel algorithm
Contact author(s)
tsukasa @ kddilabs jp
takagi @ imi kyushu-u ac jp
History
2014-01-17: last of 4 revisions
2013-06-17: received
See all versions
Short URL
https://ia.cr/2013/388
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/388,
      author = {Tsukasa Ishiguro and Shinsaku Kiyomoto and Yutaka Miyake and Tsuyoshi Takagi},
      title = {Parallel Gauss Sieve Algorithm : Solving the SVP in the Ideal Lattice of 128-dimensions},
      howpublished = {Cryptology ePrint Archive, Paper 2013/388},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/388}},
      url = {https://eprint.iacr.org/2013/388}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.