https://eprint.iacr.org/2024/555

What a lovely hat

Is it made out of tin foil?

IACR Logo
Cryptology ePrint Archive

  * Papers
        Updates from the last:
      + 7 days
      + 31 days
      + 6 months
      + 365 days
      + -------------------------------------------------------------
      + Listing by year
      + All papers
      + Compact view
      + -------------------------------------------------------------
      + How to cite
      + -------------------------------------------------------------
      + Harvesting metadata
  * Submissions
      + Submit a paper
      + Revise or withdraw a paper
      + Acceptance and publishing conditions
  * About
      + Goals and history
      + News
      + Statistics
      + Contact

Search Button
[                    ] Search
Advanced search

Paper 2024/555

Quantum Algorithms for Lattice Problems

Yilei Chen[orcid], Tsinghua University, Shanghai Artificial
Intelligence Laboratory, Shanghai Qi Zhi Institute

Abstract

We show a polynomial time quantum algorithm for solving the learning
with errors problem (LWE) with certain polynomial modulus-noise
ratios. Combining with the reductions from lattice problems to LWE
shown by Regev [J.ACM 2009], we obtain polynomial time quantum
algorithms for solving the decisional shortest vector problem
(GapSVP) and the shortest independent vector problem (SIVP) for all
$n$-dimensional lattices within approximation factors of $\tilde{\
Omega}(n^{4.5})$. Previously, no polynomial or even subexponential
time quantum algorithms were known for solving GapSVP or SIVP for all
lattices within any polynomial approximation factors. To develop a
quantum algorithm for solving LWE, we mainly introduce two new
techniques. First, we introduce Gaussian functions with complex
variances in the design of quantum algorithms. In particular, we
exploit the feature of the Karst wave in the discrete Fourier
transform of complex Gaussian functions. Second, we use windowed
quantum Fourier transform with complex Gaussian windows, which allows
us to combine the information from both time and frequency domains.
Using those techniques, we first convert the LWE instance into
quantum states with purely imaginary Gaussian amplitudes, then
convert purely imaginary Gaussian states into classical linear
equations over the LWE secret and error terms, and finally solve the
linear system of equations using Gaussian elimination. This gives a
polynomial time quantum algorithm for solving LWE.

Metadata

Available format(s)
    [file-pdf]PDF
Publication info
    Preprint.
Contact author(s)
    chenyilei ra @ gmail com
History
    2024-04-10: approved
    2024-04-10: received
    See all versions
Short URL
    https://ia.cr/2024/555
License
    Creative Commons Attribution
    CC BY

BibTeX [copy-outli]Copy to clipboard

@misc{cryptoeprint:2024/555,
      author = {Yilei Chen},
      title = {Quantum Algorithms for Lattice Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2024/555},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/555}},
      url = {https://eprint.iacr.org/2024/555}
}

IACR Logo
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.