Graph-Theoretic Algorithms for the “Isomorphism of Polynomials” Problem

Charles Bouillaguet 1 Pierre-Alain Fouque 2, 3 Amandine Véber 4
1 CALFOR - Calcul Formel
LIFL - Laboratoire d'Informatique Fondamentale de Lille
4 CMAP
CMAP - Centre de Mathématiques Appliquées
Abstract : We give three new algorithms to solve the "isomorphism of polynomial" problem, which was underlying the hardness of recovering the secret-key in some multivariate trapdoor one-way functions. In this problem, the adversary is given two quadratic functions, with the promise that they are equal up to linear changes of coordinates. Her objective is to compute these changes of coordinates, a task which is known to be harder than Graph-Isomorphism. Our new algorithm build on previous work in a novel way. Exploiting the birthday paradox, we break instances of the problem in time q 2n/3 (rigorously) and q n/2 (heuristically), where q n is the time needed to invert the quadratic trapdoor function by exhaustive search. These results are obtained by turning the algebraic problem into a combinatorial one, namely that of recovering partial information on an isomorphism between two exponentially large graphs. These graphs, derived from the quadratic functions, are new tools in multivariate crypt-analysis.
Type de document :
Communication dans un congrès
Advances in Cryptology - 2013, May 2013, Athenes, Greece. Springer, LNCS 7881, pp.17, 2013, EUROCRYPT 2013. <10.1007/978-3-642-38348-9_13>
Liste complète des métadonnées


https://hal.inria.fr/hal-00825503
Contributeur : Pierre-Alain Fouque <>
Soumis le : vendredi 12 décembre 2014 - 09:39:20
Dernière modification le : mercredi 30 août 2017 - 09:47:17
Document(s) archivé(s) le : samedi 15 avril 2017 - 08:09:23

Fichier

BFV13.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Charles Bouillaguet, Pierre-Alain Fouque, Amandine Véber. Graph-Theoretic Algorithms for the “Isomorphism of Polynomials” Problem. Advances in Cryptology - 2013, May 2013, Athenes, Greece. Springer, LNCS 7881, pp.17, 2013, EUROCRYPT 2013. <10.1007/978-3-642-38348-9_13>. <hal-00825503v2>

Partager

Métriques

Consultations de
la notice

150

Téléchargements du document

72