Paper 2023/1623

Concrete Analysis of Quantum Lattice Enumeration

Shi Bai, Florida Atlantic University
Maya-Iggy van Hoof, Ruhr University Bochum
Floyd B. Johnson, Florida Atlantic University
Tanja Lange, Eindhoven University of Technology
Tran Ngo, Florida Atlantic University

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, corresponding to lattice points as a linear combination of the lattice basis with the coefficients. This work provides a concrete analysis for the cost of quantum lattice enumeration based on Montanaro's quantum tree backtracking algorithm. More precisely, we give a concrete implementation in the quantum circuit model. We also show how to optimize the circuit depth by parallelizing the components. Based on the circuit designed, we discuss the concrete quantum resource estimates required for lattice enumeration.

Available format(s)
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
LatticesQuantum algorithmsEnumerationQuantum backtracking
Contact author(s)
Shih bai @ gmail com
iggy hoof @ rub de
johnsonf2017 @ fau edu
tanja @ hyperelliptic org
ngotbtran @ gmail com
2023-10-20: approved
2023-10-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shi Bai and Maya-Iggy van Hoof and Floyd B. Johnson and Tanja Lange and Tran Ngo},
      title = {Concrete Analysis of Quantum Lattice Enumeration},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1623},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.