Paper 2024/030
Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs
Abstract
The Learning With Errors ($\mathsf{LWE}$) problem asks to find $\mathbf{s}$ from an input of the form $(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s}+\mathbf{e}) \in (\mathbb{Z}/q\mathbb{Z})^{m \times n} \times (\mathbb{Z}/q\mathbb{Z})^{m}$, for a vector $\mathbf{e}$ that has small-magnitude entries. In this work, we do not focus on solving $\mathsf{LWE}$ but on the task of sampling instances. As these are extremely sparse in their range, it may seem plausible that the only way to proceed is to first create $\mathbf{s}$ and $\mathbf{e}$ and then set $\mathbf{b} = \mathbf{A}\mathbf{s}+\mathbf{e}$. In particular, such an instance sampler knows the solution. This raises the question whether it is possible to obliviously sample $(\mathbf{A}, \mathbf{A}\mathbf{s}+\mathbf{e})$, namely, without knowing the underlying $\mathbf{s}$. A variant of the assumption that oblivious $\mathsf{LWE}$ sampling is hard has been used in a series of works to analyze the security of candidate constructions of Succinct Non interactive Arguments of Knowledge (SNARKs). As the assumption is related to $\mathsf{LWE}$, these SNARKs have been conjectured to be secure in the presence of quantum adversaries. Our main result is a quantum polynomial-time algorithm that samples well-distributed $\mathsf{LWE}$ instances while provably not knowing the solution, under the assumption that $\mathsf{LWE}$ is hard. Moreover, the approach works for a vast range of $\mathsf{LWE}$ parametrizations, including those used in the above-mentioned SNARKs. This invalidates the assumptions used in their security analyses, although it does not yield attacks against the constructions themselves.
Metadata
- Available format(s)
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. Major revision. STOC 2024
- Keywords
- LWESNARKQuantum AlgorithmOblivious Sampling
- Contact author(s)
-
thomas debris @ inria fr
pouria fallahpour @ ens-lyon fr
damien stehle @ cryptolab co kr - History
- 2024-05-14: last of 3 revisions
- 2024-01-08: received
- See all versions
- Short URL
- https://ia.cr/2024/030
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/030, author = {Thomas Debris-Alazard and Pouria Fallahpour and Damien Stehlé}, title = {Quantum Oblivious {LWE} Sampling and Insecurity of Standard Model Lattice-Based {SNARKs}}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/030}, year = {2024}, url = {https://eprint.iacr.org/2024/030} }