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 .