Paper 2026/1345
Double-Structured Genetic Algorithm for Solving the SVP Based on Double Optimization: Using Two Types of Chromosomes
Abstract
The shortest vector problem (SVP) is central in lattice-based cryptography. In this paper, we focus on one of recent classes of algorithms for solving SVP: genetic algorithms (GAs) for lattice. In this paper, we propose the fastest GA to date for solving the SVP. From a search strategy perspective, our algorithm can be seen as an improved version of Fukase's algorithm. On the other hand, from a structure perspective, our algorithm is more than just an improved version of Fukase's algorithm. It is double-structured consisting of: (i) the inner GA, which inherits the basic structure from Fukase’s algorithm, and (ii) the outer GA, which optimizes the parameters used in the inner GA. The inner and outer GAs use mutually distinct objective functions. In our algorithm, we use two types of chromosomes and split the criterion for evaluation of chromosomes into two objective functions: the squared Euclidean norm for the inner GA and the evolution velocity of a lattice basis for the outer GA. The latter measures the velocity of the changes of the G-S sum, which is the sum of the squared lengths of the Gram-Schmidt orthogonalized vectors of a lattice basis, and is our novel criterion.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- latticeshortest vector problemgenetic algorithm (GA)
- Contact author(s)
- fukase @ mail tohoku-gakuin ac jp
- History
- 2026-07-02: approved
- 2026-06-30: received
- See all versions
- Short URL
- https://ia.cr/2026/1345
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1345,
author = {Masaharu Fukase},
title = {Double-Structured Genetic Algorithm for Solving the {SVP} Based on Double Optimization: Using Two Types of Chromosomes},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1345},
year = {2026},
url = {https://eprint.iacr.org/2026/1345}
}
