Dynamic Self-dual DeepBKZ Lattice Reduction with Free Dimensions
Dynamic Self-dual DeepBKZ Lattice Reduction with Free Dimensions
复制标题
具有自由维度的动态自对偶 DeepBKZ 晶格缩减
DOI：
10.1007/978-981-15-8061-1_30
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yasuda Masaya
中科院分区：
文献类型：
--
作者：
Nakamura Satoshi;Ikematsu Yasuhiko;Yasuda Masaya
格基约简是解决最短向量问题(SVP)等格问题的必备工具，它的难易程度保证了格密码的安全性。最著名的约简是Lenstra-Lenstra-Lovász(LLL)的著名算法，块Korkine-Zolotarev(BKZ)是它的分块推广。目前，BKZ及其变种如BKZ-2.0是评估格密码系统安全级别的事实上的标准约简算法。最近，作为对BKZ的数学改进，DeepBKZ被提出，其中具有深度插入的LLL被称为LLL子例程。在这篇文章中，我们发展了DeepBKZ的一个新的自对偶变异体来获得约化基。与传统的自对偶算法不同的是，我们选择了合适的First维度来约简原始格基和对偶格基。我们还报告了几个随机格基的实验结果，比较了我们的自对偶DeepBKZ与原始BKZ和DeepBKZ。
Lattice basis reduction is a mandatory tool to solve lattice problems such as the shortest vector problem (SVP), whose hardness assures the security of lattice-based cryptography. The most famous reduction is the celebrated algorithm by Lenstra-Lenstra–Lovász (LLL), and the block Korkine–Zolotarev (BKZ) is its blockwise generalization. At present, BKZ and its variants such as BKZ 2.0 are a de facto standard reduction algorithm to estimate the security level of lattice-based cryptosystems. Recently, DeepBKZ was proposed as a mathematical improvement of BKZ, in which LLL with deep insertions (DeepLLL) is called as a subroutine alternative to LLL. In this paper, we develop a new self-dual variant of DeepBKZ to obtain a reduced basis. Different from conventional self-dual algorithms, we select suitablefree dimensionsto reduce primal and dual lattice bases in our variant. We also report experimental results to compare our self-dual DeepBKZ with primal BKZ and DeepBKZ for several random lattice bases.