Improving genetic algorithms for solving the SVP: focusing on low memory consumption and high reproducibility
Improving genetic algorithms for solving the SVP: focusing on low memory consumption and high reproducibility
复制标题
DOI：
10.1007/s42044-022-00118-5
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Masaharu Fukase;M. Kaminaga
中科院分区：
文献类型：
--
作者：
Masaharu Fukase;M. Kaminaga
最短向量问题（SVP）在基于格的密码学中绝对重要。在本文中，我们显着改进了用于求解 SVP 的遗传算法 (GA)。 GA 是一种简单而强大的优化技术，有可能消除现有快速 SVP 算法的局限性。我们改进了 GA 构建的整个阶段。我们提出的方法基于低内存消耗和高再现性的概念，这是我们的算法与其他SVP算法之间的主要和显着的区别。我们的贡献是双重的。首先，我们开发了一种新的遗传算法来求解SVP，并在运行时性能上取得了相当大的改进。其次，我们在晶格的背景下解释了某些遗传操作，例如突变和交叉，这在以前的研究中尚未完成。本文的总体结果是我们展示了 GA 在晶格领域的潜力。
The shortest vector problem (SVP) is absolutely essential in lattice-based cryptography. In this paper, we significantly improve genetic algorithms (GAs) for solving the SVP. GAs, which are simple and powerful optimization techniques, that have the potential to eliminate the limitations of the existing fast SVP algorithms. We improve the entire phase of the GA construction. Our proposed method is based on the concept of low memory consumption and high reproducibility, and this is the main and significant difference between our algorithm and the other SVP algorithms. Our contributions are twofold. First, we developed a new GA for solving the SVP and achieved a considerable improvement in the running time performance. Second, we interpreted certain genetic operations, such as mutation and crossover, in the context of lattices, which has not been done in previous studies. The general result of this paper is that we showed the potential of GAs in the field of lattices.