On the complexity of the BKW algorithm on LWE
On the complexity of the BKW algorithm on LWE
复制标题
DOI：
10.1007/s10623-013-9864-x
复制
发表时间：
2015-02-01
影响因子：
1.6
通讯作者：
Perret, Ludovic
中科院分区：
文献类型：
--
作者：
Albrecht, Martin R.;Cid, Carlos;Perret, Ludovic
这项工作通过提供对解决 LWE 问题具体实例的数据和计算量要求的精确估计，研究了 Blum-Kalai-Wasserman (BKW) 算法应用于带错误学习 (LWE) 问题时的复杂性。我们将这种精细分析应用于文献中各种基于 LWE 的加密方案的建议参数，并与基于格约化的替代方法进行比较。因此，我们为这些基于 LWE 的方案的混凝土硬度提供了新的上限。相当令人惊讶的是，当 LWE 简化为 SIS 时，BKW 算法似乎优于从维度开始的晶格简化算法的已知估计。然而，这假设可以访问无限数量的 LWE 样本。
This work presents a study of the complexity of the Blum-Kalai-Wasserman (BKW) algorithm when applied to the Learning with Errors (LWE) problem, by providing refined estimates for the data and computational effort requirements for solving concrete instances of the LWE problem. We apply this refined analysis to suggested parameters for various LWE-based cryptographic schemes from the literature and compare with alternative approaches based on lattice reduction. As a result, we provide new upper bounds for the concrete hardness of these LWE-based schemes. Rather surprisingly, it appears that BKW algorithm outperforms known estimates for lattice reduction algorithms starting in dimension when LWE is reduced to SIS. However, this assumes access to an unbounded number of LWE samples.