...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of complexity >On the complexity of solving quadratic Boolean systems
【24h】

On the complexity of solving quadratic Boolean systems

机译：关于求解二次布尔系统的复杂性

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

摘要

A fundamental problem in computer science is that of finding all the common zeros of m quadratic polynomials in n unknowns over F_2. The cryptanalysis of several modern ciphers reduces to this problem. Up to now, the best complexity bound was reached by an exhaustive search in 4 log_2 n2~n operations. We give an algorithm that reduces the problem to a combination of exhaustive search and sparse linear algebra. This algorithm has several variants depending on the method used for the linear algebra step. We show that, under precise algebraic assumptions on the input system, the deterministic variant of our algorithm has complexity bounded by O(2~(0.841n)) when m = n, while a probabilistic variant of the Las Vegas type has expected complexity 0(2~(0.792n)). Experiments on random systems show that the algebraic assumptions are satisfied with probability very close to 1. We also give a rough estimate for the actual threshold between our method and exhaustive search, which is as low as 200, and thus very relevant for cryptographic applications.
机译：计算机科学中的一个基本问题是在F_2上的n个未知数中找到m个二次多项式的所有公零。几种现代密码的密码分析简化了这个问题。到目前为止，在4个log_2 n2〜n个操作中进行了详尽的搜索，从而达到了最佳的复杂度范围。我们给出了一种将问题简化为穷举搜索和稀疏线性代数的组合的算法。根据用于线性代数步骤的方法，该算法具有多种变体。我们表明，在输入系统的精确代数假设下，当m = n时，我们算法的确定性变量具有以O（2〜（0.841n））为边界的复杂度，而拉斯维加斯类型的概率变量具有预期的复杂度0 （2〜（0.792n））。在随机系统上进行的实验表明，代数假设的概率非常接近1。我们还对方法和穷举搜索之间的实际阈值进行了粗略估计，该阈值低至200，因此与密码学应用非常相关。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号