






















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。