Improved lattice enumeration algorithms by primal and dual reordering methods
Improved lattice enumeration algorithms by primal and dual reordering methods
复制标题
通过原始和对偶重新排序方法改进了格枚举算法
DOI：
10.1049/ise2.12083
复制
发表时间：
2022
影响因子：
1.4
通讯作者：
Fujisaki Eiichiro
中科院分区：
文献类型：
--
作者：
Yamamura Kazuki;Wang Yuntao;Fujisaki Eiichiro
基于格的密码系统的安全性通常基于最短向量问题（SVP）的难度。原始枚举（ENUM）算法求解SVP运行在指数时间，由于穷举搜索，这是作为一个子程序的块Korkin-Zolotarev（BKZ）算法。如何降低ENUM的计算复杂度是一个关键问题。在本文中，首先，我们改进了Wang等人在ACISP 2018中提出的重新排序方法。我们称我们提出的方法DPR，它置换投影的对偶格向量的减少规范。初步的实验结果表明，所提出的重新排序方法可以降低ENUM的复杂度相比，前;例如，DPR减少约32.8%，平均在45维格子。此外，作者的模拟表明，格维数越高，DPR可以减少更多的ENUM复杂度。此外，我们还研究了决定何时执行重排序方法的条件。最后，利用DPR方法和提出的条件对BKZ算法进行了改进。
The security of lattice‐based cryptosystems is generally based on the hardness of the Shortest Vector Problem (SVP). The original enumeration (ENUM) algorithm solving SVP runs in exponential time due to the exhaustive search, which is used as a subroutine for the block Korkin–Zolotarev (BKZ) algorithm. It is a critical issue to reduce the computational complexity of ENUM. In this paper, first, we improve the reordering method proposed by Wang et al. in ACISP 2018. We call our proposed method DPR, which permutates the projected dual lattice vectors by decreasing norms. Preliminary experimental results show that the proposed reordering methods can reduce the ENUM complexity compared to the predecessor; for instance, DPR reduces around 32.8% on average in 45‐dimensional lattices. Moreover, the authors’ simulation shows that the higher the lattice dimension, the more DPR can reduce the ENUM complexity. In addition, we study a condition for deciding when the reordering method shall be executed or not. Finally, we improve the BKZ algorithm with DPR methods and the proposed condition.