Welcome to the resource topic for
**2024/030**

**Title:**

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

**Authors:**
Thomas Debris-Alazard, Pouria Fallahpour, Damien Stehlé

**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 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.

**ePrint:**
https://eprint.iacr.org/2024/030

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .