Étude d'outils algébriques et combinatoires pour la cryptographie à clef publique

Cette thèse, dont le sujet est l étude d outils algébriques et combinatoires pour la cryptographie à clef publique, se place dans le contexte général de l analyse de problèmes alternatifs aux problèmes de la théorie des nombres. Ici, nous avons étudié deux types de problèmes : ceux liés à des équivalences de polynômes et ceux reliés à la combinatoire des mots. Les problèmes d Équivalence de Polynômes La cryptographie multivariée, c est-à-dire la cryptographie utilisant des polynômes à plusieurs variables, offre un éventail relativement large de problèmes difficiles. C est à un type de problèmes de cette famille qu appartiennent les problèmes d Équivalence de Polynômes. Dans la première partie de cette thèse, nous étudions deux aspects complémentaires de ces problèmes : à savoir leurs difficulté théorique et leurs résolution pratique : - D un point de vue complexité théorique, nous montrons notamment que ces problèmes sont en général au moins aussi difficiles que le problème de l Isomorphisme de Graphes. D autre part, une vision unifiée de ces problèmes nous permet de donner une preuve originale que ces problèmes ne sont pas NP-durs. - D un point de vue pratique, nous étudions un problème d Équivalence de Polynômes particulier. Nous avons appelé ce problème Équivalence Linéaire de Polynômes (PLE). Brièvement, celui-ci consiste à retrouver un changement de variables linéaire entre deux ensembles de polynômes multivariés. Notons que la difficulté de ce problème garantit la sécurité d un schéma d authentification (resp. de signature). Nous présentons pour ce problème deux types d algorithmes : le premier utilisant une approche géométrique de ce problème, et le second reposant sur une caractérisation différentielle de l Équivalence Linéaire de Polynômes. Sur la sécurité de systèmes basés sur les mots. Dans la deuxième partie de cette thèse, nous présentons le travail réalisé sur deux systèmes de chiffrement basés sur les mots. Concernant le premier schéma, celui de P.J. Abisha, D.G. Thomas et K.G. Subramanian, nous présentons deux algorithmes permettant de résoudre le problème sur lequel repose la sécurité de ce système. Dans le contexte d une attaque à chiffré choisi, nous montrons en outre comment construire efficacement une clef équivalente à la clef secrète. Finalement nous montrons que le schéma de L. Siromoney et R. Mathew est également vulnérable à une attaque à chiffré choisi. Nos résultats prouvent ainsi la faiblesse de ces deux schémasPARIS-EST Marne-la-Vallee-BU (774682101) / SudocSudocFranceF