On the complexity of the LWR-solving BKW algorithm

DOI10.1007/978-3-030-12146-4_13MaRDI QIDQ1736054zbMATH OpenOpenAlexFDO

Authors Hiroki Okada, Atsushi Takayasu, Kazuhide Fukushima, Shinsaku Kiyomoto, Tsuyoshi Takagi

Publication date 29 March 2019

Full work available at URL https://doi.org/10.1007/978-3-030-12146-4_13

zbMATH Keywords

latticelearning with errorslearning with roundingBlum-Kalai-Wasserman algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Cryptography (94A60)

Recommendations

• On the complexity of the BKW algorithm on LWE
• On the asymptotic complexity of solving LWE
• Better algorithms for LWE and LWR
• Coded-BKW with sieving
• An improved BKW algorithm for LWE with applications to cryptography and lattices

Cited in

(1)

• On the complexity of the BKW algorithm on LWE

This page was built for publication: On the complexity of the LWR-solving BKW algorithm

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