Analyzing the Crossbred Algorithm for the MQ Problem

January 31, 2025

2025

Étant donné un système polynomial de m polynômes et n variables sur un corps fini Fp, résoudre ce système est prouvé être un problème NP-complet. Les méthodes communément utilisées pour résoudre ces systèmes sont des algorithmes calculant des bases de Gröbner (F4, F5) ou basés sur l'algèbre linéaire (XL). Dans ce travail, nous nous concentrons sur le problème MQ (Multivariate Quadratic), c’est-à-dire que nous considérons des polynômes de degré 2. En particulier, nous nous intéressons au cas où le système polynomial est défini sur F2. Dans ce cas, une recherche exhaustive (FES) devient une méthode viable pour résoudre le système polynomial.

Une autre approche consiste à spécifier certaines variables et à tenter de résoudre les systèmes résultants via une approche algébrique. C'est l'idée derrière Crossbred [JV17], par exemple. Crossbred est l’un des algorithmes les plus efficaces en pratique, avec des implémentations battant des records lors du Fukuoka MQ challenge. Cependant, la complexité théorique de cet algorithme n’est pas bien comprise. Les auteurs affirment qu’elle est similaire à celle de FXL ou BooleanSolve, mais à notre connaissance, cette conjecture reste à prouver.

L'objectif principal de ce travail est donc de mieux comprendre cet algorithme. Dans cette optique, nous proposons une variante de l’algorithme Crossbred basée sur l’algorithme matrix-F5 tel que décrit dans [Bar04], afin de faciliter son analyse.

Lors de ma présentation, je décrirai cette nouvelle variante de l’algorithme Crossbred, y compris une analyse sur le choix des paramètres pour cette variante et une compréhension plus approfondie de l’algorithme. À partir des résultats obtenus sur la variante, nous déduisons une analyse de l’algorithme Crossbred original.

  • [Bar04] Magali Bardet. Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. Thèse de doctorat, Université Paris 6, 2004.
  • [JV17] Antoine Joux and Vanessa Vitse. A crossbred algorithm for solving boolean polynomial systems. In Number-Theoretic Methods in Cryptology - NuTMiC 2017, volume 10737 of Lecture Notes in Computer Science, pages 3–21. Springer, 2017.