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.
Next sessions
-
Encryption homomorphe sans bruit à l'aide de groupes
Speaker : Pierre Guillot - Ravel Technologies (dispo Université de Strasbourg, IRMA)
Je vais rappeler les travaux de Nuida et Ostrovski sur l'utilisation des groupes pour l'élaboration de schémas cryptographiques homomorphes. Je vais présenter nos travaux qui fournissent des encodages à la fois plus efficaces et plus généraux, et qui déterminent exactement quels groupes peuvent être utilisés. Puis je vais discuter GRAFHEN, un protocole qui utilise ces idées. Je dirai juste[…]-
Cryptography
-