Paper 2017/372

A crossbred algorithm for solving Boolean polynomial systems

Antoine Joux and Vanessa Vitse

Abstract

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).

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
multivariate polynomial systemsGroebner basisXLmultivariate cryptographyalgebraic cryptanalysis
Contact author(s)
vanessa vitse @ univ-grenoble-alpes fr
History
2017-04-28: received
Short URL
https://ia.cr/2017/372
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/372,
      author = {Antoine Joux and Vanessa Vitse},
      title = {A crossbred algorithm for solving Boolean polynomial systems},
      howpublished = {Cryptology ePrint Archive, Paper 2017/372},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/372}},
      url = {https://eprint.iacr.org/2017/372}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.