Cryptanalyse de Fonctions de Hachage par Résolution de Systèmes Polynomiaux avec des Résultants

Au cours de la dernière décennie, l’introduction de protocoles cryptographiques avancés opérant sur de grands corps finis Fq et requérant des modélisations arithmétiques simples des fonctions utilisées a créé le besoin de primitives cryptographiques efficaces dans ce cadre, communément appelées Arithmetization-Oriented (AO).

La cryptanalyse des fonctions de hachage AO repose essentiellement sur l’étude du problème CICO appliqué à la permutation sous-jacente,
et l’approche la plus efficace pour le résoudre (à part le brute-force) consiste en pratique à résoudre des systèmes polynomiaux multivariés.

Deux travaux récents, présentés à Crypto 2024 et Asiacrypt 2024, ont réussi à résoudre le problème CICO sur plusieurs fonctions de hachage AO reposant sur des S-boxes à inverse de faible degré, de manière bien plus efficace que les méthodes classiques basées sur les bases de Gröbner, en utilisant respectivement des techniques avancées de bases de Gröbner et des résultants.

Dans cette présentation, nous résumons l’approche et les résultats d’un papier publié à Crypto 2025 qui améliore considérablement ces deux travaux récents, « Improved Resultant Attack against
Arithmetization-Oriented Primitives ». Nous étudierons un cadre d’attaque fondé sur le calcul de résultants, applicable à un large éventail de permutations AO.