Quantum Augmented Dual Attack. (arXiv:2205.13983v2 [quant-ph] UPDATED)

Web: http://arxiv.org/abs/2205.13983

We present a quantum augmented variant of the dual lattice attack on the
Learning with Errors (LWE) problem, using classical memory with quantum random
access (QRACM). Applying our results to lattice parameters from the literature,
we find that our algorithm outperforms previous algorithms, assuming unit cost
access to a QRACM. On a technical level, we show how to obtain a quantum
speedup on the search for Fast Fourier Transform (FFT) coefficients above a
given threshold by leveraging the relative sparseness …

attack quantum