Improved lattice enumeration algorithms by primal and dual reordering methods
Abstract 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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2023-01-01
|
| Series: | IET Information Security |
| Online Access: | https://doi.org/10.1049/ise2.12083 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Abstract 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. |
|---|---|
| ISSN: | 1751-8709 1751-8717 |