La cryptographie multivariée peut être définie comme la cryptographie à clé publique basée sur la difficulté de résoudre des systèmes polynomiaux à plusieurs variables. Bien que la recherche de tels schémas soit apparue dès le début des années 80, elle s'est surtout développée depuis une dizaine d'années, et a conduit à plusieurs propositions jugées promet-teuses, telles que le cryptosystème HFE et le schéma de signature SFLASH. Les shémas multivariés se posent ainsi en alternative possible aux schémas traditionnels basés sur des problèmes de théorie des nombres, et constituent des solutions efficaces pour l'implantation des fonctionnalités de la cryptographie à clé publique. Lors d'Eurocrypt 2005, Fouque, Granboulan et Stern ont proposé une nouvelle approche cryptanalytique pour les schémas multivariés basée sur l'étude d'invariants liés à la différentielle, et ont démontré la pertinence de cette approche par la cryptanalyse du schéma PMI proposé par Ding. Au cours de cette thèse, nous avons développé l'approche différentielle proposée par Fouque et al. dans deux directions. La première consiste en un traitement combinatoire des invariants dimensionnels de la différentielle. Ceci nous a permis de montrer qu'une clé publique HFE pouvait être distinguée d'un système quadratique aléatoire en temps quasipolynomial. Une seconde application de cette même approche nous a permis de cryptanalyser une variation de HFE proposée par Ding et Schmidt à PKC 2005. Le second développement de la thèse est la découverte d'invariants fonctionnels de la différentielle et nous a permis de montrer la faiblesse du schéma SFLASH.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00811529 |
| Date | 27 September 2007 |
| Creators | Dubois, Vivien |
| Publisher | Université Pierre et Marie Curie - Paris VI |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0017 seconds