• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Number-theoretic methods in cryptology >A Crossbred Algorithm for Solving Boolean Polynomial Systems
【24h】

A Crossbred Algorithm for Solving Boolean Polynomial Systems

机译：求解布尔多项式系统的杂交算法

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

摘要

We consider the problem of solving multivariate systems of Boolean polynomial equations: starting from a system of m polynomials of degree at most d in n variables, we want to find its solutions over F_2. Except for d = 1, the problem is known to be NP-hard, and its hardness has been used to create public cryptosystems; this motivates the search for faster algorithms to solve this problem. After reviewing the state of the art, we describe a new algorithm and show that it outperforms previously known methods in a wide range of relevant parameters. In particular, the first named author has been able to solve all the Fukuoka Type I MQ challenges, culminating with the resolution of a system of 148 quadratic equations in 74 variables in less than a day (and with a lot of luck).
机译：我们考虑解决布尔多项式方程的多元系统的问题：从n个变量中最多d个d的m个多项式的系统开始，我们想在F_2上找到它的解。除了d = 1之外，已知该问题是NP困难的，其硬度已用于创建公共密码系统。这促使人们寻求更快的算法来解决该问题。在回顾了现有技术之后，我们描述了一种新算法，并表明它在广泛的相关参数方面优于先前已知的方法。特别是，第一位作者能够解决所有Fukuoka I类MQ难题，并最终在不到一天的时间内（包括很多运气）解决了由148个二次方程式组成的74个变量的系统。

著录项

  • 来源
  • 会议地点 Warsaw(PL)
  • 作者

    Antoine Joux; Vanessa Vitse;

  • 作者单位

    Chaire de Cryptologie de la Fondation de l'UPMC, Sorbonne Universites, UPMC Univ Paris 06, CNRS, LIP6 UMR 7606, Paris, France;

    Institut Fourier, Universite Grenoble-Alpes, Grenoble, France;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号