Paper 2023/1498
LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling
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
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 AlgorithmsLearning with ErrorsLattices
- 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} }