Quantum Lattice Enumeration in Limited Depth, Fernando Virdia

Speakers: Fernando Virdia
Host: Michael Naehrig

In 2018, Aono, Nguyen, and Shen (ASIACRYPT 2018) proposed to use quantum backtracking algorithms (Montanaro, TOC 2018; Ambainis and Kokainis, STOC 2017) to speedup lattice point enumeration. 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 quantum lattice point sieving. In this talk, we will 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.