Paper 2023/1423
Quantum Lattice Enumeration in Limited Depth
Abstract
In 2018, Aono et al. (ASIACRYPT 2018) proposed to use quantum backtracking algorithms (Montanaro, TOC 2018; Ambainis and Kokainis, STOC 2017) to speedup lattice point enumeration. Quantum lattice sieving algorithms had already been proposed (Laarhoven et al., PQCRYPTO 2013), being shown to provide an asymptotic speedup over classical counterparts, but also to lose competitiveness at dimensions relevant to cryptography if practical considerations on quantum computer architecture were taken into account (Albrecht et al., ASIACRYPT 2020). Aono et al.'s work argued that quantum walk speedups can be applied to lattice enumeration, achieving at least a quadratic asymptotic speedup à la Grover search while not requiring exponential amounts of quantum accessible classical memory, as it is the case for sieving. In this work, we explore how to lower bound the cost of using Aono et al.'s techniques on lattice enumeration with extreme cylinder pruning, assuming a limit to the maximum depth that a quantum computation can achieve without decohering, with the objective of better understanding the practical applicability of quantum backtracking in lattice cryptanalysis.
Note: Full version of the paper published at CRYPTO 2024.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published by the IACR in CRYPTO 2024
- Keywords
- lattice enumerationquantum cryptanalysisquantum walkbacktracking algorithmpost-quantum
- Contact author(s)
-
nina bindel @ sandboxaq com
xavier bonnetain @ inria fr
marcel tiepelt @ kit edu
f virdia @ gmx com - History
- 2024-06-18: last of 2 revisions
- 2023-09-20: received
- See all versions
- Short URL
- https://ia.cr/2023/1423
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1423,
author = {Nina Bindel and Xavier Bonnetain and Marcel Tiepelt and Fernando Virdia},
title = {Quantum Lattice Enumeration in Limited Depth},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1423},
year = {2023},
url = {https://eprint.iacr.org/2023/1423}
}