International Association for Cryptologic Research

International Association
for Cryptologic Research


Concrete Analysis of Quantum Lattice Enumeration

Shi Bai , Florida Atlantic University, USA
Maya-Iggy van Hoof , Ruhr University Bochum, Germany
Floyd B. Johnson , Florida Atlantic University, USA
Tanja Lange , Eindhoven University of Technology, Netherlands
Tran Ngo , Florida Atlantic University, USA
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
Abstract: 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 needs to find 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 the quantum tree backtracking algorithm of Montanaro (ToC, '18). More precisely, we give a concrete implementation of Montanaro's algorithm for lattice enumeration based on 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.
  title={Concrete Analysis of Quantum Lattice Enumeration},
  author={Shi Bai and Maya-Iggy van Hoof and Floyd B. Johnson and Tanja Lange and Tran Ngo},