Concrete Analysis of Quantum Lattice Enumeration

ePrint Report: Concrete Analysis of Quantum Lattice Enumeration

Shi Bai, Maya-Iggy van Hoof, Floyd B. Johnson, Tanja Lange, Tran Ngo

Lattice reduction algorithms such as BKZ (Block-Korkine-Zolotarev) play a central role in estimating the security of lattice-based cryptography. The subroutine in BKZ which finds the shortest vector in a projected sublattice can be instantiated with enumeration algorithms. The enumeration procedure can be seen as a depth-first search on some ``enumeration tree'' whose nodes denote a partial assignment of the coefficients, …

algorithms analysis block concrete cryptography enumeration eprint report johnson maya ngo play quantum report role security shi van