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

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

Abstract

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.

Details

Authors
Organisations
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

• Other Electrical Engineering, Electronic Engineering, Information Engineering
Original language English IEEE International Symposium on Information Theory (ISIT) IEEE - Institute of Electrical and Electronics Engineers Inc. Published - 2019 Research Yes 2019 IEEE International Symposium on Information Theory - Paris, FranceDuration: 2019 Jul 7 → 2019 Jul 12https://2019.ieee-isit.org/

Conference

Conference 2019 IEEE International Symposium on Information Theory ISIT France Paris 2019/07/07 → 2019/07/12 https://2019.ieee-isit.org/