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

DOI10.1109/TIT.2019.2906233zbMath1432.94134OpenAlexW2900465852WikidataQ128187453 ScholiaQ128187453MaRDI QIDQ5224145

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

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)

Related Items

Making the BKW algorithm practical for LWE ⋮ 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 ⋮ Algebraic Aspects of Solving Ring-LWE, Including Ring-Based Improvements in the Blum--Kalai--Wasserman Algorithm