Learning with errors and extrapolated dihedral cosets

DOI10.1007/978-3-319-76581-5_24MaRDI QIDQ1753874zbMATH OpenOpenAlexFDO

Authors Zvika Brakerski, Elena Kirshanova, Damien Stehlé, Weiqiang Wen

Publication date 29 May 2018

Full work available at URL https://arxiv.org/abs/1710.08223

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

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.

Recommendations

• Classical hardness of learning with errors
• On the concrete hardness of learning with errors
• An improved quantum algorithm for the quantum learning with errors problem
• Quantum algorithms for variants of average-case lattice problems via filtering
• A hybrid lattice basis reduction and quantum search attack on LWE

Cited in

(9)

• Augmented Learning with Errors: The Untapped Potential of the Error Term
• Leveraging the hardness of dihedral coset problem for quantum cryptography
• An improved quantum algorithm for the quantum learning with errors problem
• Quantum algorithms for typical hard problems: a perspective of cryptanalysis
• Counting extensional differences in BC-learning
• Quantum algorithms for variants of average-case lattice problems via filtering
• Quantum search-to-decision reduction for the LWE problem
• Estimated cost for solving generalized learning with errors problem via embedding techniques
• Post-quantum \(\kappa\)-to-1 trapdoor claw-free functions from extrapolated dihedral cosets

This page was built for publication: Learning with errors and extrapolated dihedral cosets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1753874)