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

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 O( √ n) -time algorithm for S|LWE⟩ with Gaussian amplitude with known phase, given 2 O( √ 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.