Cryptographie basée sur les codes : des instances difficiles pour les problèmes de décodage

La sécurité des schémas cryptographiques à clef publique couramment utilisés repose sur la difficulté de problèmes de théorie des nombres. Mais depuis la découverte de l'algorithme quantique de Shor en 1994, on sait qu'un ordinateur quantique pourrait résoudre ces problèmes en temps polynomial. De là la nécessité de construire des primitives cryptographiques dont la sécurité repose sur des problèmes qui résistent à l'ordinateur quantique. Un des principaux candidats est le problème de décodage, qui est à la base de la cryptographie basée sur les codes correcteurs d'erreur. Cette thèse est une contribution pour améliorer la confiance que l'on peut avoir en la difficulté de ce problème et en ses applications cryptographiques. En premier lieu, grâce à une réduction pire cas-cas moyen, nous démontrons qu'à partir d'un code arbitraire quelconque il est possible de générer des distributions pseudoaléatoires de codes aussi dures à décoder que le code arbitraire préalablement choisi. Nous prouvons ce résultat pour la métrique de Hamming, puis nous l'adaptons au problème de décodage en métrique rang. Dans les deux cas le principal outil pour obtenir la réduction est la construction de codes pseudoaléatoires dont la distance minimale est linéaire. En second lieu, nous construisons un schéma de chiffrement à clef publique en métrique rang dont la sécurité repose uniquement sur des hypothèses de sécurité classiques et qui possède la particularité d'avoir une clef publique statistiquement indistinguable de l'uniforme pour certaines zones de paramètres. Cette construction se base sur une généralisation des codes LRPC (Low Rank Parity Check) et sur l'approche multidimensionnelle qui consiste à décoder simultanément plusieurs mots de codes paratageant le même support. Nous améliorons également la borne supérieur théorique de la probabilité d'erreur lors du décodage des codes LRPC.