Quantum Lattice Enumeration in Limited Depth

ePrint Report: Quantum Lattice Enumeration in Limited Depth

Nina Bindel, Xavier Bonnetain, Marcel Tiepelt, Fernando Virdia

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 …

algorithms asiacrypt enumeration eprint report point quantum report xavier