TY - GEN
T1 - Practical Improvements on BKZ Algorithm
AU - Zhao, Ziyu
AU - Ding, Jintai
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - Lattice problems such as NTRU and LWE problems are widely used as the security base of post-quantum cryptosystems. And currently, lattice reduction by BKZ algorithm is the most efficient way to solve them. In this paper, we give four further improvements on BKZ algorithm, which can be used for SVP subroutines based on enumeration and sieving. These improvements in combination provide a speed-up of 23-4 in total. So all the lattice-based NIST PQC candidates lose 3–4 bits of security in concrete attacks. Using these new techniques, we solved the 656 and 700 dimensional ideal lattice challenges in 380 and 1787 thread hours, respectively. The cost of the first one (also used an enumeration-based SVP subroutine) is much less than the previous records (4600 thread hours). One can still simulate the improved BKZ algorithm to find the blocksize strategy that makes Pot of the basis (defined in Sect. 4.2) decrease as fast as possible, which means the length of the first basis vector decrease the fastest if we accept the GSA assumption. It is useful for analyzing concrete attacks on lattice-based cryptography.
AB - Lattice problems such as NTRU and LWE problems are widely used as the security base of post-quantum cryptosystems. And currently, lattice reduction by BKZ algorithm is the most efficient way to solve them. In this paper, we give four further improvements on BKZ algorithm, which can be used for SVP subroutines based on enumeration and sieving. These improvements in combination provide a speed-up of 23-4 in total. So all the lattice-based NIST PQC candidates lose 3–4 bits of security in concrete attacks. Using these new techniques, we solved the 656 and 700 dimensional ideal lattice challenges in 380 and 1787 thread hours, respectively. The cost of the first one (also used an enumeration-based SVP subroutine) is much less than the previous records (4600 thread hours). One can still simulate the improved BKZ algorithm to find the blocksize strategy that makes Pot of the basis (defined in Sect. 4.2) decrease as fast as possible, which means the length of the first basis vector decrease the fastest if we accept the GSA assumption. It is useful for analyzing concrete attacks on lattice-based cryptography.
KW - BKZ algorithm
KW - Lattice reduction
KW - Lattice-based cryptography
UR - http://www.scopus.com/inward/record.url?scp=85164914487&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-34671-2_19
DO - 10.1007/978-3-031-34671-2_19
M3 - Conference Proceeding
AN - SCOPUS:85164914487
SN - 9783031346705
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 273
EP - 284
BT - Cyber Security, Cryptology, and Machine Learning - 7th International Symposium, CSCML 2023, Proceedings
A2 - Dolev, Shlomi
A2 - Gudes, Ehud
A2 - Paillier, Pascal
PB - Springer Science and Business Media Deutschland GmbH
T2 - 7th International Symposium on Cyber Security, Cryptology, and Machine Learning, CSCML 2023
Y2 - 29 June 2023 through 30 June 2023
ER -