The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors
This is an incremental improvement for cryptographic security analysis, specifically targeting post-quantum cryptography researchers and practitioners.
The paper tackles the problem of solving the Learning with Errors (LWE) problem, a key for post-quantum cryptography, by improving the coded-BKW with sieving algorithm through the use of different reduction factors in sieving steps, resulting in an asymptotic complexity of 2^{0.8917n} compared to the previous best of 2^{0.8927n}.
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 $σ= n^{1.5}/(\sqrt{2π}\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.