4.4 Article

On the complexity of the BKW algorithm on LWE

期刊

DESIGNS CODES AND CRYPTOGRAPHY
卷 74, 期 2, 页码 325-354

出版社

SPRINGER
DOI: 10.1007/s10623-013-9864-x

关键词

Learning with errors; BKW; LPN; FHE

资金

  1. Royal Society [JP090728]
  2. Commission of the European Communities through the ICT program [ICT-2007-216676 (ECRYPT-II)]
  3. Computer Algebra and Cryptography (CAC) project [ANR-09-JCJCJ-0064-01]
  4. HPAC grant of the French National Research Agency
  5. US Army Research Laboratory
  6. UK Ministry of Defence [W911NF-06-3-0001]

向作者/读者索取更多资源

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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.4
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据