Paper 2024/030
Quantum Oblivious LWE Sampling and Insecurity of Standard Model LatticeBased 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 smallmagnitude 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 polynomialtime algorithm that samples welldistributed $\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 abovementioned 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 @ enslyon fr
damien stehle @ cryptolab co kr  History
 20240514: last of 3 revisions
 20240108: received
 See all versions
 Short URL
 https://ia.cr/2024/030
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/030, author = {Thomas DebrisAlazard and Pouria Fallahpour and Damien Stehlé}, title = {Quantum Oblivious {LWE} Sampling and Insecurity of Standard Model LatticeBased {SNARKs}}, howpublished = {Cryptology ePrint Archive, Paper 2024/030}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/030}}, url = {https://eprint.iacr.org/2024/030} }