Paper 2023/1623
Concrete Analysis of Quantum Lattice Enumeration
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 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.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2023
- Keywords
- LatticesQuantum algorithmsEnumerationQuantum backtracking
- Contact author(s)
-
Shih bai @ gmail com
iggy hoof @ rub de
johnsonf2017 @ fau edu
tanja @ hyperelliptic org
ngotbtran @ gmail com - History
- 2023-10-20: approved
- 2023-10-19: received
- See all versions
- Short URL
- https://ia.cr/2023/1623
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1623,
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},
url = {https://eprint.iacr.org/2023/1623}
}