Paper 2023/1498
On the Hardness of $\sf{S|LWE\rangle}$ with Gaussian and Other Amplitudes
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, show quantum algorithms for those variants, or prove they are as hard as standard LWE. To this end, Chen, Liu, and Zhandry [Eurocrypt 2022] define the $\sf{S|LWE\rangle}$ problem, which encodes the error of LWE samples into quantum amplitudes. They then show efficient quantum algorithms for $\sf{S|LWE\rangle}$ with a few interesting amplitudes. However, the hardness of the most interesting amplitude, Gaussian, was not addressed by Chen et al., or only known for some restricted settings (for example, when the number of $\sf{S|LWE\rangle}$ samples is very small, it is well known that $\sf{S|LWE\rangle}$ is as hard as standard LWE). In this paper, we show new hardness and algorithms for $\sf{S|LWE\rangle}$ with Gaussian and other amplitudes. Our main results are 1. There exist quantum reductions from standard LWE or worst-case GapSVP to $\sf{S|LWE\rangle}$ with Gaussian amplitude with unknown phase, and arbitrarily many $\sf{S|LWE\rangle}$ samples. 2. There is a $2^{\widetilde{O}(\sqrt{n})}$-time algorithm for $\sf{S|LWE\rangle}$ with Gaussian amplitude with known phase, given $2^{\widetilde{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. One way of interpreting our result is: to show a sub-exponential time quantum algorithm for standard LWE, all we need is to handle phases in $\sf{S|LWE\rangle}$ amplitudes better, either in the algorithm or the reduction.
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
- 2023-10-03: approved
- 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 = {On the Hardness of $\sf{S|LWE\rangle}$ with Gaussian and Other Amplitudes}, howpublished = {Cryptology ePrint Archive, Paper 2023/1498}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1498}}, url = {https://eprint.iacr.org/2023/1498} }