The Learning With Errors (LWE) problem asks to find s from an input of the form (A, b = As + e) ∈ (Z/qZ)^{m×n} × (Z/qZ)^{m}, for a vector e that has small-magnitude entries. In this work, we do not focus on solving 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 s and e and then set b = As + e. In particular, such an instance sampler knows the solution. This raises the question whether it is possible to obliviously sample (A, As+e), namely, without knowing the underlying s. A variant of the assumption that oblivious 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 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 LWE instances while provably not knowing the solution, under the assumption that LWE is hard. Moreover, the approach works for a vast range of LWE parametrizations, including those used in the above-mentioned SNARKs.
I am a PhD student at ENS Lyon under the supervision of Prof. Damien Stehlé. I am interested in a wide range of topics in theoretical computer science. I am currently working on qunatum cryptanalysis of lattice-based primitives.