Analysis of DeepBKZ reduction for finding short lattice vectors
Analysis of DeepBKZ reduction for finding short lattice vectors
复制标题
用于寻找短晶格向量的 DeepBKZ 约简分析
DOI：
10.1007/s10623-020-00765-4
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yamaguchi Junpei
中科院分区：
文献类型：
--
作者：
Yasuda Masaya;Nakamura Satoshi;Yamaguchi Junpei
格基约简是解决最短向量问题等格问题的必备工具。其中Lenstra–Lenstra–Lovász约简算法（LLL）最为著名，其典型改进是块Korkine–Zolotarev算法和带有深度插入的LLL算法（DeepLLL），均由Schnorr和Euchner提出。在具有块大小的 BKZ 中，在枚举之前多次调用 LLL 以减少格基，以在每个维度的块格中找到最短的非零向量。最近，“DeepBKZ”被提出作为 BKZ 的数学改进，其中 DeepLLL 被称为 LLL 的子程序替代。在本文中，我们从理论和实践上分析了 DeepBKZ 的输出质量。具体来说，我们给出了 DeepBKZ 特有的可证明上限。我们还开发了“DeepBKZ 2.0”，它是 DeepBKZ 与 BKZ 2.0 一样的改进，并展示了实验结果，它在实践中发现了比 BKZ 2.0 更短的晶格向量。
Lattice basis reduction is a mandatory tool for solving lattice problems such as the shortest vector problem. The Lenstra–Lenstra–Lovász reduction algorithm (LLL) is the most famous, and its typical improvements are the block Korkine–Zolotarev algorithm and LLL with deep insertions (DeepLLL), both proposed by Schnorr and Euchner. In BKZ with blocksize, LLL is called many times to reduce a lattice basis before enumeration to find a shortest non-zero vector in every block lattice of dimension. Recently, “DeepBKZ” was proposed as a mathematical improvement of BKZ, in which DeepLLL is called as a subroutine alternative to LLL. In this paper, we analyze the output quality of DeepBKZ in both theory and practice. Specifically, we give provable upper bounds specific to DeepBKZ. We also develop “DeepBKZ 2.0”, an improvement of DeepBKZ like BKZ 2.0, and show experimental results that it finds shorter lattice vectors than BKZ 2.0 in practice.
阻止 Korkin-Zolotarev 基底和连续最小值
影响因子：
2.8
作者：
SuccessiveMinimaC;P.;SchnorrUniversitt;FrankfurtFachbereich;Mathematik;InformatikFebruary
通讯作者：
InformatikFebruary