On the Asymptotics of Solving the LWE Problem Using Coded-BKW With Sieving

DOI10.1109/TIT.2019.2906233MaRDI QIDQ5224145zbMATH OpenOpenAlexWikidataFDO

Authors Qian Guo, Thomas Johansson, Erik Mårtensson, Paul Stankovski Wagner

Publication date 19 July 2019

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tit.2019.2906233

zbMATH Keywords

asymptotic performance of solution algorithmBlum-Kalai- Wasserman (BKW) algorithmlearning with errors problem (LWE)sieving in lattices

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Cryptography (94A60)

Cited in

(7)

• On the asymptotic complexity of solving LWE
• Making the BKW algorithm practical for LWE
• On the complexity of the BKW algorithm on LWE
• Algebraic aspects of solving ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm
• A non-heuristic approach to time-space tradeoffs and optimizations for BKW
• Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms
• Memory-efficient BKW algorithm for solving the LWE problem

This page was built for publication: On the Asymptotics of Solving the LWE Problem Using Coded-BKW With Sieving

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