Practical Cryptanalysis of the Identification Scheme Based on the Isomorphism of Polynomial With One Secret Problem

Charles Bouillaguet 1 Jean-Charles Faugère 2 Pierre-Alain Fouque 1, 3, 4 Ludovic Perret 5
1 LIENS - Laboratoire d'informatique de l'école normale supérieure
2 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
3 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
4 ENS Paris - École normale supérieure - Paris
5 LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : This paper presents a practical cryptanalysis of the Identification Scheme proposed by Patarin at Crypto 1996. This scheme relies on the hardness of the Isomorphism of Polynomial with One Secret (IP1S), and enjoys shorter key than many other schemes based on the hardness of a combinatorial problem (as opposed to number-theoretic problems). Patarin proposed concrete parameters that have not been broken faster than exhaustive search so far. On the theoretical side, IP1S has been shown to be harder than Graph Isomorphism, which makes it an interesting target. We present two new deterministic algorithms to attack the IP1S problem, and we rigorously analyze their complexity and success probability. We show that they can solve a (big) constant fraction of all the instances of degree two in polynomial time. We verified that our algorithms are very efficient in practice. All the parameters with degree two proposed by Patarin are now broken in a few seconds. The parameters with degree three can be broken in less than a CPU-month. The identification scheme is thus quite badly broken.
Type de document :
Communication dans un congrès
Dario Catalano; Nelly Fazio; Rosario Gennaro; Antonio Nicolosi. 14th IACR International Conference on Practice and Theory of Public Key Cryptography - PKC 2011, Mar 2011, Taormina, Italy. Springer, 6571, pp.473-493, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-19379-8_29〉
Liste complète des métadonnées

Littérature citée [46 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00556671
Contributeur : Pierre-Alain Fouque <>
Soumis le : lundi 17 janvier 2011 - 15:35:37
Dernière modification le : jeudi 22 novembre 2018 - 14:25:25
Document(s) archivé(s) le : jeudi 30 juin 2011 - 13:48:29

Fichier

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

Identifiants

Collections

INRIA | ENS-PARIS | UPMC | LIP6 | PSL | INRIA-ROCQ | SORBONNE-UNIVERSITE

Citation

Charles Bouillaguet, Jean-Charles Faugère, Pierre-Alain Fouque, Ludovic Perret. Practical Cryptanalysis of the Identification Scheme Based on the Isomorphism of Polynomial With One Secret Problem. Dario Catalano; Nelly Fazio; Rosario Gennaro; Antonio Nicolosi. 14th IACR International Conference on Practice and Theory of Public Key Cryptography - PKC 2011, Mar 2011, Taormina, Italy. Springer, 6571, pp.473-493, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-19379-8_29〉. 〈inria-00556671〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

543

Téléchargements de fichiers

257

Contact


archive-ouverte@inria.fr