he hardness of the learning with errors (LWE) problem is one of the

most fruitful resources of modern cryptography. In particular, it is one

of the most prominent candidates for secure post-quantum cryptography.

Understanding its quantum complexity is therefore an important goal. We

show that under quantum polynomial time reductions, LWE is equivalent to

a relaxed version of the dihedral coset problem (DCP), which we call

extrapolated DCP (eDCP). The extent of extrapolation varies with the LWE

noise rate. By considering different extents of extrapolation, our

result generalizes Regev's famous proof that if DCP is in BQP (quantum

poly-time) then so is LWE (FOCS'02). We also discuss a connection

between eDCP and Childs and Van Dam's algorithm for generalized hidden

shift problems (SODA'07). Our result implies that a BQP solution for LWE

might not require the full power of solving DCP, but rather only a

solution for its relaxed version, eDCP, which could be easier.

This is a joint work with Zvika Brakerski, Elena Kirshanova and Damien

Stehlé.