Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem
Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem
复制标题
适合大规模并行化的快速格基约简及其在最短向量问题中的应用
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Goichiro Hanaoka
中科院分区：
文献类型：
--
作者：
Tadanori Teruya;K. Kashiwabara;Goichiro Hanaoka
格最短向量问题的难度是许多基于格的密码系统安全性的基本假设，因此，评估其难度是很重要的。在这里，最近在研究大规模晶格计算问题的难度方面取得的进展表明，需要研究开发大规模并行计算环境性能的设计和方法。本文提出了一种适用于大规模并行化的格基约简算法。我们的并行化策略是Fukase-Kashiwabara算法的扩展（J. Information Processing, Vol. 23, No. 1, 2015）。在我们的算法中，给定一个格基作为输入，生成格基的变体，然后每个过程对其格基进行约简；此时，进程之间相互协作，共享辅助信息，以加速格基约简。此外，为了减少正交基向量的平方和，我们提出了一种基于格基评价函数的新策略。我们将算法应用于高级副总裁挑战赛中的问题实例。通过使用大型集群，我们在大约394天内解决了一个150维的问题实例，我们还解决了维度为134、138、140、142、144、146和148的问题实例。由于之前的世界纪录是132维的问题，这些结果证明了我们的建议的有效性。
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.