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

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

Thomas Debris-Alazard, Pouria Fallahpour, Damien Stehlé

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 …

eprint report errors find input insecurity oblivious problem quantum report standard thomas