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!
|
| _version_ | 1850166823410991104 |
|---|---|
| author | Kazuki Yamamura Yuntao Wang Eiichiro Fujisaki |
| author_facet | Kazuki Yamamura Yuntao Wang Eiichiro Fujisaki |
| author_sort | Kazuki Yamamura |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-daa6d9bc2c3b4858a9f1929db3c0d177 |
| institution | OA Journals |
| issn | 1751-8709 1751-8717 |
| language | English |
| publishDate | 2023-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | IET Information Security |
| spelling | doaj-art-daa6d9bc2c3b4858a9f1929db3c0d1772025-08-20T02:21:20ZengWileyIET Information Security1751-87091751-87172023-01-01171354510.1049/ise2.12083Improved lattice enumeration algorithms by primal and dual reordering methodsKazuki Yamamura0Yuntao Wang1Eiichiro Fujisaki2NTT Social Informatics Laboratories Tokyo JapanGraduate School of Engineering Osaka University Suita JapanSchool of Information Science Japan Advanced Institute of Science and Technology Nomi JapanAbstract 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.https://doi.org/10.1049/ise2.12083 |
| spellingShingle | Kazuki Yamamura Yuntao Wang Eiichiro Fujisaki Improved lattice enumeration algorithms by primal and dual reordering methods IET Information Security |
| title | Improved lattice enumeration algorithms by primal and dual reordering methods |
| title_full | Improved lattice enumeration algorithms by primal and dual reordering methods |
| title_fullStr | Improved lattice enumeration algorithms by primal and dual reordering methods |
| title_full_unstemmed | Improved lattice enumeration algorithms by primal and dual reordering methods |
| title_short | Improved lattice enumeration algorithms by primal and dual reordering methods |
| title_sort | improved lattice enumeration algorithms by primal and dual reordering methods |
| url | https://doi.org/10.1049/ise2.12083 |
| work_keys_str_mv | AT kazukiyamamura improvedlatticeenumerationalgorithmsbyprimalanddualreorderingmethods AT yuntaowang improvedlatticeenumerationalgorithmsbyprimalanddualreorderingmethods AT eiichirofujisaki improvedlatticeenumerationalgorithmsbyprimalanddualreorderingmethods |