ANR PRC POSTCRYPTUM

Cryptanalyse algébrique pour la cryptographie post-quantum

Projet en collaboration avec le MIS (porteur du projet) et le LIP6.

Parmi les techniques bien établies en cryptanalyse, les attaques algébriques sont des méthodes permettant de décrire le schéma comme un système d’équations polynomiales, et par conséquent de réduire sa sécurité à la difficulté de résoudre le système associé. POSTCRYPTUM vise à concevoir des attaques algébriques efficaces, pour plusieurs classes de cryptosystèmes qui peuvent être modélisés comme un système polynomial binaire. Plusieurs méthodes peuvent être envisagées pour résoudre des systèmes polynomiaux multivariés sur des champs finis. L’une d’elles est l’algorithme de base de Gröbner, qui s’est révélé être un outil puissant pour la cryptanalyse en 2003, lorsqu’il a été utilisé pour résoudre un défi HFE. Depuis lors, ils ont été largement utilisés en cryptographie. Cependant, l’algorithme de base de Gröbner a une complexité exponentielle et dans le cas binaire, des résultats expérimentaux sur des schémas de cryptographie multivariés ont montré que la recherche exhaustive de Bouillaguet et al. et la méthode de croisement de Joux-Vitse donnent de meilleurs résultats que l’approche à base de Gröbner.

En outre, nous notons que le cas des systèmes booléens peut également être traité comme un problème de satisfiabilité, puisque les polynômes booléens peuvent être utilisés pour représenter les contraintes. Une fois cette transformation effectuée, on peut utiliser les solveurs SAT pour énumérer les solutions de la formule logique correspondante. Dans ce dernier cas, des résultats prometteurs ont été obtenus dans la thèse de Monika Trimoska, sur l’attaque du calcul de l’indice pour le logarithme discret des courbes elliptiques. L’approche n’est pas nouvelle, puisque des tentatives d’utilisation de solveurs SAT pour des problèmes de cryptanalyse ont été faites dans le passé pour d’autres cryptosystèmes, principalement pour les chiffrement par flux. Cependant, les techniques de satisfiabilité restent peu connues et peu explorées par les cryptographes. De plus, la plupart des solveurs SAT ont été conçus pour répondre à des problèmes industriels de grande taille et ils ignorent complètement la nature algébrique des instances cryptographiques.

Plus d’informations sur le site web du projet