密码学报（中英文）2025，Vol.12Issue(1)：215-226,12.DOI:10.13868/j.cnki.jcr.000758
求解格上最短向量问题的自适应遗传算法
An Adaptive Genetic Algorithm for Solving the Shortest Vector Problem on Lattice
摘要
Abstract
The shortest vector problem(SVP)is a classic hard problem in lattice-based cryptography.In 2015,Ding et al.proposed the first genetic algorithm that is capable of solving the SVP.This algorithm uses the orthogonal representation of the BKZ-reduced basis to search the space composed of lattice points,and can efficiently find the shortest vector within the lattice.Nevertheless,this algorithm adopts fixed crossover and mutation rates,which makes it prone to getting trapped in local optimal solutions.Moreover,it does not fully utilize the sparse characteristics of short vectors under the orthogonal representation of the BKZ-reduced basis.This study improves the intelligent SVP solution of the algorithm from three dimensions:breaking away from local optimal solutions,the algorithm convergence speed,and the success probability.A module for dynamically calculating the crossover and mutation rates is applied.Specifically,two dimensions,namely,the individual quality and the population convergence degree,are mainly considered to control the crossover and mutation rates,so as to prevent the algorithm from getting trapped in local optimal solutions.An adaptive mutation strategy is designed,which fully exploits the sparsity of the orthogonal integer representation of short vectors under the BKZ-reduced basis at the gene level,thus accelerating the convergence speed of the entire algorithm.A multi-population parallel genetic algorithm is proposed to improve the success rate of the probabilistic algorithm.关键词
格理论/遗传算法/最短向量问题Key words
lattice theory/genetic algorithm/shortest vector problem(SVP)分类
信息技术与安全科学引用本文复制引用
毕经国,苏磊,王林..求解格上最短向量问题的自适应遗传算法[J].密码学报（中英文）,2025,12(1):215-226,12.基金项目
国家重点研发计划(2024YFB4504700,2022YFB2902202) （2024YFB4504700,2022YFB2902202）
保密通信全国重点实验室基金(2024,6142103042408) （2024,6142103042408）
北京邮电大学青年科技创新人才支持计划(2023ZCJH10)National Key Research and Development Program of China(2024YFB4504700,2022YFB2902202) （2023ZCJH10）
National Key Laboratory of Security Communication Foundation(2024,6142103042408) （2024,6142103042408）
Youth Science and Technol-ogy Innovation Talent Support Program of Beijing University of Posts and Telecommunications(2023ZCJH10) （2023ZCJH10）
