Development and analysis of massive parallelization of a lattice basis reduction algorithm
Development and analysis of massive parallelization of a lattice basis reduction algorithm
复制标题
格基约简算法大规模并行化的开发与分析
DOI：
10.1007/s13160-023-00580-z
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Katsuki Fujiwara
中科院分区：
文献类型：
--
作者：
Nariaki Tateiwa;Yuji Shinano;Masaya Yasuda;Shizuo Kaji;Keiichiro Ymamura;Katsuki Fujiwara
格密码的安全性依赖于格问题求解的难度。格基约简是求解格问题的有力工具，而块Korkine-Zolotarev（BKZ）约简算法是密码分析中事实上的标准。提出了一种基于随机化的BKZ型约简并行算法。输入格基的随机副本被并行地独立地减少，而几个基向量在所有进程之间异步地共享。在随机化和信息共享之间有一个权衡;如果大量的信息被共享，所有的进程可能都在处理同一个问题，这就减少了并行化的好处。为了监控随机性和共享之间的平衡，我们提出了一个新的度量来量化各种各样的晶格基，我们经验性地找到了一个最佳的参数共享高维晶格。我们还证明了我们的并行算法和度量的有效性，通过实验从多个角度。
The security of lattice-based cryptography relies on the hardness of solving lattice problems. Lattice basis reduction is a strong tool for solving lattice problems, and the block Korkine–Zolotarev (BKZ) reduction algorithm is the de facto standard in cryptanalysis. We propose a parallel algorithm of BKZ-type reduction based on randomization. Randomized copies of an input lattice basis are independently reduced in parallel, while several basis vectors are shared asynchronously among all processes. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes might work on the same problem, which diminishes the benefit of parallelization. To monitor the balance between randomness and sharing, we propose a new metric to quantify the variety of lattice bases, and we empirically find an optimal parameter of sharing for high-dimensional lattices. We also demonstrate the effectiveness of our parallel algorithm and metric through experiments from multiple perspectives.
用于寻找短晶格向量的 DeepBKZ 约简分析
DOI：
10.1007/s10623-020-00765-4
发表时间：
2020
期刊：
Designs, Codes and Cryptography
影响因子：
--
作者：
Yasuda Masaya;Nakamura Satoshi;Yamaguchi Junpei
通讯作者：
Yamaguchi Junpei