TY - GEN
T1 - Faster enumeration-based lattice reduction
T2 - 40th Annual International Cryptology Conference, CRYPTO 2020
AU - Albrecht, Martin R.
AU - Bai, Shi
AU - Fouque, Pierre Alain
AU - Kirchner, Paul
AU - Stehlé, Damien
AU - Wen, Weiqiang
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2020.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - We give a lattice reduction algorithm that achieves root Hermite factor k1/(2k) in time kk/8+o(k) and polynomial memory. This improves on the previously best known enumeration-based algorithms which achieve the same quality, but in time kk/(2e) + o(k). A cost of kk/8 + o(k) was previously mentioned as potentially achievable (Hanrot-Stehlé’10) or as a heuristic lower bound (Nguyen’10) for enumeration algorithms. We prove the complexity and quality of our algorithm under a heuristic assumption and provide empirical evidence from simulation and implementation experiments attesting to its performance for practical and cryptographic parameter sizes. Our work also suggests potential avenues for achieving costs below kk/8 + o(k) for the same root Hermite factor, based on the geometry of SDBKZ-reduced bases.
AB - We give a lattice reduction algorithm that achieves root Hermite factor k1/(2k) in time kk/8+o(k) and polynomial memory. This improves on the previously best known enumeration-based algorithms which achieve the same quality, but in time kk/(2e) + o(k). A cost of kk/8 + o(k) was previously mentioned as potentially achievable (Hanrot-Stehlé’10) or as a heuristic lower bound (Nguyen’10) for enumeration algorithms. We prove the complexity and quality of our algorithm under a heuristic assumption and provide empirical evidence from simulation and implementation experiments attesting to its performance for practical and cryptographic parameter sizes. Our work also suggests potential avenues for achieving costs below kk/8 + o(k) for the same root Hermite factor, based on the geometry of SDBKZ-reduced bases.
UR - https://www.scopus.com/pages/publications/85089722039
U2 - 10.1007/978-3-030-56880-1_7
DO - 10.1007/978-3-030-56880-1_7
M3 - Conference contribution
AN - SCOPUS:85089722039
SN - 9783030568795
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 186
EP - 212
BT - Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings
A2 - Micciancio, Daniele
A2 - Ristenpart, Thomas
PB - Springer
Y2 - 17 August 2020 through 21 August 2020
ER -