Séminaire LJK-Modèles et Algorithmes Déterministes: BIPOP-CASYS

 

Le Jeudi 23 Février 2012 à 9h45 en Salle 1 - Tour IRMA

 

Séminaire de Mr Ayoub OTMANI (Université de Caen)

 

Approche algébrique sur la sécurité de la cryptographie fondée sur les codes

 

Résumé:

 

La cryptographie fondée sur la théorie des codes correcteurs d’erreurs est apparue avec les travaux de McEliece. Il fut le premier à proposer un cryptosystème à clef publique utilisant les codes. En particulier, il proposa d'utiliser les codes de Goppa (classiques) qui sont connus pour avoir un algorithme de décodage efficace. Son travail fait suite aux résultats de Berlekamp, McEliece, et van Tilborg qui ont montré que le problème de décodage d'un code aléatoire est un problème NP-difficile. Ce fait fournit une première indication sur la difficulté d'un des problèmes les plus importants en théorie des codes. D'autre part, plusieurs articles ont cherché à proposer des algorithmes pour le résoudre le plus efficacement possible. Tous ont une complexité exponentielle. Ces résultats accréditent l'idée que le décodage d’un code aléatoire est un bon candidat pour bâtir des primitives cryptographiques sûres. Ce point est renforcé par les résultats de Shor qui montrent que dans le modèle de calcul quantique les problèmes de factorisation et du logarithme discret deviennent faciles, alors que le problème de décodage resterait difficile.

Bien qu'aussi ancien que le tout premier cryptosystème à clef publique qu'est RSA, le cryptosystème de McEliece est un schéma peu utilisé sans doute en raison des tailles des clefs publiques. D'autre part, de par sa nature même qui est de type sac-à-dos, ce schéma a reçu peu d'attention en raison des nombreuses cryptanalyses qu’ont subies les schéma de type sac-à-dos. Pourtant, ce cryptosystème n’a connu à ce jour aucune attaque remettant en cause sa sécurité.

Cet exposé fera un rappel sur les concepts généraux sur lesquels la cryptographie fondée sur la théorie des codes s'appuient pour proposer des primitives. Nous aborderons plus particulièrement la question de la sécurité en nous intéresserant soit à des cryptanalyses qui retrouvent les secrets, soit en étudiant un problème que l'on rencontre d’emblée dans ce domaine, à savoir le problème d'"indifférentiabilité" des codes de Goppa. Ce problème représente en effet actuellement une brique importante, voire essentielle, pour élaborer des preuves de sécurité pour plusieurs primitives.