Paper 2024/030

Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs

Thomas Debris-Alazard, Inria Saclay - Île-de-France Research Centre, Computer Science Laboratory of the École Polytechnique
Pouria Fallahpour, École Normale Supérieure de Lyon
Damien Stehlé, Cryptolab Inc., Lyon, France

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 constructing Succinct Non-interactive 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 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.

Available format(s)
Attacks and cryptanalysis
Publication info
LWESNARKQuantum AlgorithmOblivious Sampling
Contact author(s)
thomas debris @ inria fr
pouria fallahpour @ ens-lyon fr
damien stehle @ cryptolab co kr
2024-01-08: approved
2024-01-08: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.