Parallel Gauss Sieve Algorithm: Solving the SVP Challenge over a 128-Dimensional Ideal Lattice
Parallel Gauss Sieve Algorithm: Solving the SVP Challenge over a 128-Dimensional Ideal Lattice
复制标题
并行高斯筛算法：解决 128 维理想格子上的 SVP 挑战
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
T. Takagi
中科院分区：
文献类型：
--
作者：
T. Ishiguro;S. Kiyomoto;Yutaka Miyake;T. Takagi
在本文中，我们报告说，我们已经在TU Darmstadt的理想晶格挑战中解决了128维晶格的SVP挑战，该晶格目前是有史以来解决的挑战中最高的维度。基于晶格的密码学的安全性是基于解决晶格中最短的向量问题SVP的硬度。 2010年，Micciancio和Voulgaris提出了一种高斯筛子算法，用于使用降低高斯载体的L列表来启发SVP。米尔德（Milde）和施耐德（Schneider）为高斯筛子算法提出了一种并行实施方法。但是，由于每个线程的分布式列表中出现了大量的非高斯向量，因此实现中10多个线程的效率降低了。在本文中，我们提出了一种更实用的并行性高斯筛子算法。我们的算法部署了分配给每个线程的样品向量的额外的高斯列表V v，并且列表中的所有向量l通过使用V中的所有样品向量互相减少高斯。对于大尺寸，开销很小。最后，我们成功地解决了通过大约30,000个CPU小时，通过环形多项式X128+1产生的128维理想晶格解决了SVP挑战。
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 x128+1 using about 30,000 CPU hours.