The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding


The Learning with Errors problem (LWE) is one of the main candidates for post-quantum cryptography. At Asiacrypt 2017, coded-BKW with sieving, an algorithm combining the Blum-Kalai-Wasserman algorithm (BKW) with lattice sieving techniques, was proposed. In this paper, we improve that algorithm by using different reduction factors in different steps of the sieving part of the algorithm. In the Regev setting, where $q = n^2$ and $\sigma = n^{1.5}/(\sqrt{2\pi}\log_2^2 n)$, the asymptotic complexity is $2^{0.8917n}$, improving the previously best complexity of $2^{{0.8927n}}$. When a quantum computer is assumed or the number of samples is limited, we get a similar level of improvement.


Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Other Electrical Engineering, Electronic Engineering, Information Engineering
Original languageEnglish
Title of host publicationIEEE International Symposium on Information Theory (ISIT)
PublisherIEEE - Institute of Electrical and Electronics Engineers Inc.
Publication statusPublished - 2019
Publication categoryResearch
Event2019 IEEE International Symposium on Information Theory - Paris, France
Duration: 2019 Jul 72019 Jul 12


Conference2019 IEEE International Symposium on Information Theory
Abbreviated titleISIT
Internet address