  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.
