LJK-Deterministic Models and Algorithms: BIBOP-CASYS Seminar

 

On Thursday February 23 2012 at 9h45 in Room 1 - IRMA Tower

 

Seminary of Mr Ayoub OTMANI (Université de Caen)

 

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

 

Summary

 

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.