Paper 2018/044

Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem

Tadanori Teruya, Kenji Kashiwabara, and Goichiro Hanaoka

Abstract

The hardness of the shortest vector problem for lattices is a fundamental assumption underpinning the security of many lattice-based cryptosystems, and therefore, it is important to evaluate its difficulty. Here, recent advances in studying the hardness of problems in large-scale lattice computing have pointed to need to study the design and methodology for exploiting the performance of massive parallel computing environments. In this paper, we propose a lattice basis reduction algorithm suitable for massive parallelization. Our parallelization strategy is an extension of the Fukase-Kashiwabara algorithm~(J. Information Processing, Vol. 23, No. 1, 2015). In our algorithm, given a lattice basis as input, variants of the lattice basis are generated, and then each process reduces its lattice basis; at this time, the processes cooperate and share auxiliary information with each other to accelerate lattice basis reduction. In addition, we propose a new strategy based on our evaluation function of a lattice basis in order to decrease the sum of squared lengths of orthogonal basis vectors. We applied our algorithm to problem instances from the SVP Challenge. We solved a 150-dimension problem instance in about 394 days by using large clusters, and we also solved problem instances of dimensions 134, 138, 140, 142, 144, 146, and 148. Since the previous world record is the problem of dimension 132, these results demonstrate the effectiveness of our proposal.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in PKC 2018
Keywords
lattice basis reductionmassive parallelizationshortest vector problemSVP Challenge
Contact author(s)
tadanori teruya @ aist go jp
kashiwa @ idea c u-tokyo ac jp
hanaoka-goichiro @ aist go jp
History
2018-01-10: received
Short URL
https://ia.cr/2018/044
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/044,
      author = {Tadanori Teruya and Kenji Kashiwabara and Goichiro Hanaoka},
      title = {Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2018/044},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/044}},
      url = {https://eprint.iacr.org/2018/044}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.