Description
Le problème d'isomorphisme de polynômes à deux secrets (IP2S) pour m=2 variables sur un corps k est le suivant: étant données deux familles a, b de deux polynômes quadratiques chacune, trouver deux applications linéaires bijectives s, t telles que b = t ° a ° s. Nous donnons un algorithme permettant de calculer s, t en un temps O(n^4) pour toutes les instances.<br/> Le problème IP2S a été introduit dans le domaine cryptographique par J. Patarin en 1996. Le cas particulier restreint à t=1 est le problème d'isomorphisme de polynômes à un secret (IP1S). Les instances aléatoires de IP1S sont en pratique résolues par les solveurs algébriques génériques, utilisant les bases de Gröbner. Indépendamment, une méthode algébrique permettait déjà de traiter les cas particuliers «cycliques» de IP1S. Nous étendons ici cette méthode en une solution polynomiale de toutes les instances de IP1S, en donnant une classification complète des paires de formes quadratiques sur un corps fini. Finalement, nous montrons comment retrouver le second secret de IP1S en un temps polynomial.