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 \(\mathsf {S|LWE\rangle }\) and \(\mathsf {C|LWE\rangle }\) 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 \(\mathsf {S|LWE\rangle }\) and \(\mathsf {C|LWE\rangle }\) with real Gaussian, Gaussian with linear or quadratic phase terms, and other related amplitudes. Let n be the dimension, q be the modulus of LWE samples. Our main results are

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Yilei Chen,
  • Zihan Hu,
  • Qipeng Liu,
  • Han Luo,
  • Yaxin Tu

摘要

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 \(\mathsf {S|LWE\rangle }\) and \(\mathsf {C|LWE\rangle }\) 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 \(\mathsf {S|LWE\rangle }\) and \(\mathsf {C|LWE\rangle }\) with real Gaussian, Gaussian with linear or quadratic phase terms, and other related amplitudes. Let n be the dimension, q be the modulus of LWE samples. Our main results are