Table of contents

  • This session has been presented September 26, 2014.

Description

  • Speaker

    Jérôme Plût - ANSSI

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.

Next sessions

  • Schéma de signature à clé publique : Frobénius-UOV

    • May 29, 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Gilles Macario-Rat - Orange

    L'exposé présente un schéma de signature à clé publique post-quantique inspiré du schéma UOV et introduisant un nouvel outil : les formes de Frobénius. L'accent est mis sur le rôle et les propriétés des formes de Frobénius dans ce nouveau schéma : la simplicité de description, la facilité de mise en oeuvre et le gain inédit sur les tailles de signature et de clé qui bat RSA-2048 au niveau de[…]
Show previous sessions