BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Learning With Errors and Extrapolated Dihedral Cosets
DTSTART;VALUE=DATE-TIME:20180116T130000Z
DTEND;VALUE=DATE-TIME:20180116T140000Z
DTSTAMP;VALUE=DATE-TIME:20190422T100300Z
UID:indico-event-3104@indico.math.cnrs.fr
DESCRIPTION: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 cryptograp
hy. Understanding its quantum complexity is therefore an important goal. W
e show that under quantum polynomial time reductions\, LWE is equivalent t
o a relaxed version of the dihedral coset problem (DCP)\, which we call ex
trapolated DCP (eDCP). The extent of extrapolation varies with the LWE noi
se rate. By considering different extents of extrapolation\, our result ge
neralizes Regev's famous proof that if DCP is in BQP (quantum poly-time) t
hen so is LWE (FOCS'02). We also discuss a connection between eDCP and Chi
lds 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 fu
ll power of solving DCP\, but rather only a solution for its relaxed versi
on\, eDCP\, which could be easier.\n\nThis is a joint work with Zvika Bra
kerski\, Elena Kirshanova and Damien Stehlé.\n\nhttps://indico.math.cnrs.
fr/event/3104/
LOCATION:Limoges XR203
URL:https://indico.math.cnrs.fr/event/3104/
END:VEVENT
END:VCALENDAR