LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling

Yilei Chen; Zihan Hu; Qipeng Liu; Han Luo; Yaxin Tu

Paper 2023/1498

LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling

Yilei Chen

, Tsinghua University, Shanghai Artificial Intelligence Laboratory, Shanghai Qi Zhi Institute

Zihan Hu, École Polytechnique Fédérale de Lausanne

Qipeng Liu, University of California, San Diego

Han Luo, Tsinghua University

Yaxin Tu, Princeton University

Abstract

The learning with errors problem (LWE) is one of the most important building blocks for post-quantum cryptography. To better understand the quantum hardness of LWE, it is crucial to explore quantum variants of LWE. To this end, Chen, Liu, and Zhandry [Eurocrypt 2022] defined S|LWE> and C|LWE> problems by encoding the error of LWE samples into quantum amplitudes, and showed efficient quantum algorithms for a few interesting amplitudes. However, algorithms or hardness results of the most interesting amplitude, Gaussian, were not addressed before. In this paper, we show new algorithms, hardness results and applications for S|LWE> and C|LWE> with real Gaussian, Gaussian with linear or quadratic phase terms, and other related amplitudes. Let n be the dimension of LWE samples. Our main results are 1. There is a $2^{\tilde{O}(\sqrt{n})}$-time algorithm for S|LWE> with Gaussian amplitude with known phase, given $2^{\tilde{O}(\sqrt{n})}$ many quantum samples. The algorithm is modified from Kuperberg's sieve, and in fact works for more general amplitudes as long as the amplitudes and phases are completely known. 2. There is a polynomial time quantum algorithm for solving S|LWE> and C|LWE> for Gaussian with quadratic phase amplitudes, where the sample complexity is as small as $\tilde{O}(n)$. As an application, we give a quantum oblivious LWE sampler where the core quantum sampler requires only quasi-linear sample complexity. This improves upon the previous oblivious LWE sampler given by Debris-Alazard, Fallahpour, Stehlé [STOC 2024], whose core quantum sampler requires $\tilde{O}(nr)$ sample complexity, where $r$ is the standard deviation of the error. 3. There exist polynomial time quantum reductions from standard LWE or worst-case GapSVP to S|LWE> with Gaussian amplitude with small unknown phase, and arbitrarily many samples. Compared to the first two items, the appearance of the unknown phase term places a barrier in designing efficient quantum algorithm for solving standard LWE via S|LWE>.

Note: Add new results for solving S|LWE>, C|LWE> with complex Gaussian amplitudes, and showing their applications in quantum oblivious LWE sampling.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: Quantum Algorithms Learning with Errors Lattices
Contact author(s): chenyilei @ mail tsinghua edu cn
huzihan423 @ gmail com
qipengliu0 @ gmail com
luohan23 @ mails tsinghua edu cn
yaxin tu @ princeton edu
History: 2024-10-06: revised; 2023-10-01: received; See all versions
Short URL: https://ia.cr/2023/1498
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1498,
      author = {Yilei Chen and Zihan Hu and Qipeng Liu and Han Luo and Yaxin Tu},
      title = {{LWE} with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1498},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1498}
}