Description
Date depot: 1 janvier 1900
Titre: Cryptanalyse algébrique des primitives fondées sur la théorie des codes
Directeur de thèse:
Jean-Charles FAUGÈRE (LIP6)
Directeur de thèse:
Ludovic PERRET (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Contexte général
La cryptographie fondée sur les codes exploite des problèmes difficiles émanant de la théorie des codes pour concevoir des primitives cryptographiques. Elle utilise notamment le problème de décodage d'un code aléatoire qui est réputé pour être un problème difficile. De plus, elle offre une alternative compétitive aux algorithmes qui reposent sur des problèmes issus de la théorie des nombres, en offrant des primitives qui sont parmi les plus rapides actuellement. On la qualifie aussi de cryptographie post-quantique dans la mesure où, contrairement au RSA par exemple, sa sécurité ne serait pas remise en cause avec l'apparition de la machine quantique.
Le cryptosystème de McEliece est le premier schéma basé sur le codes, et le plus célèbre. C'est un schéma de chiffrement asymétrique inventé en 1978 par R. J. McEliece. En particulier, il a suggéré d'utiliser des codes de Goppa binaires. Ce système repose sa sécurité sur la difficulté d'inverser la fonction de chiffrement, et en particulier, sur la difficulté de retrouver la clef privée à partir de données publiques. Depuis son apparition, il résiste à toute tentative de cryptanalyse, notamment aux attaques dédiées qui inversent la fonction de chiffrement. Cette voie utilise des algorithmes généraux de décodage qui s'applique à n'importe quel code, en particulier à des codes structurés comme le sont les codes de Goppa. Ce point de vue utilise les meilleurs algorithmes connus de décodage de codes aléatoires. C'est une question qui a longuement étudiée et analysée depuis plusieurs dizaines d'années. Il est donc peu probable que l'on assiste à de réelles avancées dans ce domaine.
En revanche, quasiment aucun progrès n'a été constaté autour du problème de retrouver la clef privée à partir uniquement de données publiques. Cet état de fait a poussé à affirmer qu'un code de Goppa ne présente pas de structure visible qui soit exploitable par un attaquant. Cela a amené à définir une nouvelle hypothèse sécuritaire très forte qui consiste à dire qu'il n'existe pas d'attaques qui soient simplement en mesure de distinguer entre une matrice d'un code de Goppa et une matrice tirée aléatoirement selon la loi uniforme. Ce nouvelle problème s'appelle l'indistinguabilité des codes de Goppa. Cette hypothèse est devenue depuis essentielle pour réduire la sécurité du cryptosystème de McEliece au fameux problème de décodage des codes aléatoires. Il a fallu attendre les travaux de [1] pour assister à une première définition d'un cadre théorique précis qui permette d'analyser la difficulté de résoudre le problème de recherche de la clef privée. Il est en effet montré que le problème de retrouver la clef privée est équivalent à celui de résoudre un système algébrique de type Vandermonde généralisé. Cette approche algébrique ne se limite d'ailleurs pas qu'au système de McEliece mais aussi à des variantes dites compactes qui proposent des matrices génératrices présentant des structures particulières comme la cyclicité, la dyadicité, etc. Il a été montré que certaines de ces variantes dites compactes sont faibles car vulnérables à une attaque algébrique [1], et constitue donc une technique générale et complètement nouvelle pour analyser la sécurité de schémas de type McEliece. D'autre part, cette approche a montré qu'on pouvait construire un distingueur algébrique efficace de codes de Goppa qui ont un rendement relativement élevé, ce qui représente en soi une avancée théorique notable quant à une meilleure compréhension de la structure des codes de Goppa, et par la même occasion la sécurité du cryptosystème de McEliece.
Travail envisagé
Le travail de thèse envisagé consistera à poursuivre l'approche algébrique développé dans [1]. L'approche proposée par la cryptanalyse algébrique qui utilise les technique de calcul de bases de Groebner n'est pas envisageable en l'état actuel de nos connaissances contre le schéma initial de McEliece. Le principal obstacle étant le taille du système à résoudre. Toutefois, les systèmes qui apparaissent possèdent une structure très riche (bi-homogène, sur-déterminé) qui n'est pas complètement exploitée. Dans un premier temps, l'objectif est de proposer une analyse de complexité fine des attaques algébriques contre les primitives cryptographiques fondés sur la théorie des codes en s'inspirant des résultats récents donnés dans [2]. L'objectif est de de proposer une méthode de résolution dédiéé aux primitives cryptographiques fondés sur la théorie des codes.
On s'intéressera en particulier à des variantes de McEliece utilisant des matrices structurées qui peuvent être vues comme des modifications simplifiées du système original afin de faciliter l'analyse. On portera aussi un intérêt tout particulier à analyser la sécurité de schémas de signature fondés sur les codes car les paramètres utilisés semblent favorables pour une attaque algébrique (en particulier, le système algébrique est très sur-déterminé). On s'inté
Doctorant.e: Urvoy De Portzamparc Frederic