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é, École Normale Supérieure de Lyon, Cryptolab Inc.
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.