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 constructing Succinct Noninteractive Arguments of Knowledge (SNARKs) in the standard model. 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.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Preprint.
 Keywords
 LWESNARKQuantum AlgorithmOblivious Sampling
 Contact author(s)

thomas debris @ inria fr
pouria fallahpour @ enslyon fr
damien stehle @ cryptolab co kr  History
 20240108: approved
 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} }