Title: Learning With Errors and Extrapolated Dihedral Cosets,
Abstract: The 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.