• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Designs, Codes and Crytography >On the asymptotic complexity of solving LWE
【24h】

On the asymptotic complexity of solving LWE

机译：关于求解LWE的渐近复杂性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We provide for the first time an asymptotic comparison of all known algorithms for the search version of the Learning with Errors (LWE) problem. This includes an analysis of several lattice-based approaches as well as the combinatorial BKW algorithm. Our analysis of the lattice-based approaches defines a general framework, in which the algorithms of Babai, Lindner-Peikert and several pruning strategies appear as special cases. We show that within this framework, all lattice algorithms achieve the same asymptotic complexity. For the BKW algorithm, we present a refined analysis for the case of only a polynomial number of samples via amplification, which allows for a fair comparison with lattice-based approaches. Somewhat surprisingly, such a small number of samples does not make the asymptotic complexity significantly inferior, but only affects the constant in the exponent. As the main result we obtain that both, lattice-based techniques and BKW with a polynomial number of samples, achieve running time for n-dimensional LWE, where we make the constant hidden in the big- notion explicit as a simple and easy to handle function of all LWE-parameters. In the lattice case this function also depends on the time to compute a BKZ lattice basis with block size . Thus, from a theoretical perspective our analysis reveals how LWE 's complexity changes as a function of the LWE-parameters, and from a practical perspective our analysis is a useful tool to choose LWE-parameters resistant to all currently known attacks.
机译：我们首次提供了有关错误学习（LWE）问题的搜索版本的所有已知算法的渐进比较。这包括对几种基于格的方法以及组合BKW算法的分析。我们对基于格的方法的分析定义了一个通用框架，其中Babai，Lindner-Peikert和几种修剪策略的算法作为特例出现。我们证明，在此框架内，所有晶格算法均实现相同的渐近复杂度。对于BKW算法，我们仅针对通过放大进行多项式采样的情况进行了精确分析，从而可以与基于格的方法进行合理的比较。令人惊讶的是，如此少量的样本不会使渐近复杂性明显变差，而只会影响指数中的常数。作为主要结果，我们获得了基于格的技术和具有多项式样本数量的BKW，都实现了n维LWE的运行时间，其中我们将隐藏在大概念中的常数作为一种简单且易于处理的方法进行了明确显示。所有LWE参数的功能。在晶格情况下，此函数还取决于计算具有块大小的BKZ晶格基础的时间。因此，从理论的角度来看，我们的分析揭示了LWE的复杂度如何随LWE参数的变化而变化，从实际的角度来看，我们的分析是选择抵抗所有当前已知攻击的LWE参数的有用工具。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号