Learning With Errors and Extrapolated Dihedral Cosets
This addresses the quantum complexity of LWE, a key problem for post-quantum cryptography, by linking it to a potentially simpler relaxed problem, though it is incremental as it builds on prior reductions.
The paper shows that the learning with errors (LWE) problem is equivalent under quantum reductions to a relaxed version called extrapolated dihedral coset problem (eDCP), generalizing Regev's earlier result and suggesting that solving LWE might only require solving eDCP, which could be easier.
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.