Paper 2023/1423

Quantum Lattice Enumeration in Limited Depth

Nina Bindel, SandboxAQ
Xavier Bonnetain, Université de Lorraine, CNRS, Inria
Marcel Tiepelt, KASTEL, Karlsruhe Institute of Technology
Fernando Virdia, NOVA LINCS, DI, FCT, Univerisdade NOVA de Lisboa

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 competitivity at relevant dimensions 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.

Available format(s)
Attacks and cryptanalysis
Publication info
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
2023-09-25: revised
2023-09-20: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.