A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths
A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths
复制标题
LLL 的一种新多项式时间变体，具有深度插入，可减少 Gram-Schmidt 长度的平方和
DOI：
10.1007/s10623-019-00634-9
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Yamaguchi Junpei
中科院分区：
文献类型：
--
作者：
Yasuda Masaya;Yamaguchi Junpei
格基约简算法已用于密码分析。最著名的算法是 LLL，由 Lenstra、Lenstra、Lovász 提出，其典型改进之一是带有深度插入的 LLL（DeepLLL）。 DeepLLL 减少的基础是 LLL 减少的，因此其质量至少与 LLL 一样好。在实践中，DeepLLL 通常会输出比 LLL 更简化的基，但尚不清楚理论结果。首先，我们展示了 DeepLLL 的可证明输出质量，严格优于 LLL。其次，作为本文的主要工作，我们提出了 DeepLLL 的新变体。基的 Gram-Schmidt 长度的平方和与格问题（例如最短向量问题（SVP））的计算难度有关。给定输入基础，我们的变体在每次深度插入时单调地将平方和减少给定的因子。这保证了我们的变体在多项式时间内运行。
Lattice basis reduction algorithms have been used in cryptanalysis. The most famous algorithm is LLL, proposed by Lenstra, Lenstra, Lovász, and one of its typical improvements is LLL with deep insertions (DeepLLL). A DeepLLL-reduced basis is LLL-reduced, and hence its quality is at least as good as LLL. In practice, DeepLLL often outputs a more reduced basis than LLL, but no theoretical result is known. First, we show provable output quality of DeepLLL, strictly better than that of LLL. Second, as a main work of this paper, we propose a new variant of DeepLLL. The squared-sum of Gram–Schmidt lengths of a basis is related with the computational hardness of lattice problems such as the shortest vector problem (SVP). Given an input basis, our variant monotonically decreases the squared-sum by a given factor at every deep insertion. This guarantees that our variant runs in polynomial-time.