BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Learning With Errors and Extrapolated Dihedral Cosets
DTSTART:20180116T130000Z
DTEND:20180116T140000Z
DTSTAMP:20241102T010500Z
UID:indico-event-3104@indico.math.cnrs.fr
DESCRIPTION:Speakers: Wei Weiqiang (ENS Lyon)\n\nThe hardness of the learn
ing with errors (LWE) problem is one of the most fruitful resources of mod
ern cryptography. In particular\, it is one of the most prominent candidat
es for secure post-quantum cryptography. Understanding its quantum complex
ity is therefore an important goal. We show that under quantum polynomial
time reductions\, LWE is equivalent to a relaxed version of the dihedral c
oset problem (DCP)\, which we call extrapolated DCP (eDCP). The extent of
extrapolation varies with the LWE noise rate. By considering different ext
ents of extrapolation\, our result generalizes Regev's famous proof that i
f DCP is in BQP (quantum poly-time) then so is LWE (FOCS'02). We also disc
uss a connection between eDCP and Childs and Van Dam's algorithm for gener
alized hidden shift problems (SODA'07). Our result implies that a BQP solu
tion 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.\n\
nThis is a joint work with Zvika Brakerski\, Elena Kirshanova and Damien
Stehlé.\n\nhttps://indico.math.cnrs.fr/event/3104/
LOCATION:XR203 (Limoges)
URL:https://indico.math.cnrs.fr/event/3104/
END:VEVENT
END:VCALENDAR