Quantum Augmented Dual Attack

Martin R. Albrecht; Yixin Shen

Paper 2022/656

Quantum Augmented Dual Attack

Martin R. Albrecht, Royal Holloway University of London

Yixin Shen

, Royal Holloway University of London

Abstract

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 of the FFT and using quantum amplitude estimation. We also discuss the applicability of the Quantum Fourier Transform in this context. Furthermore, we give a more rigorous analysis of the classical and quantum expected complexity of guessing part of the secret vector where coefficients follow a discrete Gaussian (mod \(q\)).

Note: Error in the code of the previous version and updates to the estimates in the paper.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Learning with Errors Dual attack Fast Fourier Transform Quantum algorithms Amplitude Estimation
Contact author(s): martin albrecht @ rhul ac uk
yixin shen @ rhul ac uk
History: 2023-01-05: last of 2 revisions; 2022-05-27: received; See all versions
Short URL: https://ia.cr/2022/656
License: CC BY

BibTeX

@misc{cryptoeprint:2022/656,
      author = {Martin R. Albrecht and Yixin Shen},
      title = {Quantum Augmented Dual Attack},
      howpublished = {Cryptology ePrint Archive, Paper 2022/656},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/656}},
      url = {https://eprint.iacr.org/2022/656}
}