Protocoles cryptographiques basés sur les codes correcteurs d’erreur en métrique rang

La plupart des protocoles cryptographiques actuels reposent sur des problèmes mathématiques que l’on considère difficiles pour les ordinateurs classiques, mais qui pourraient être résolus efficacement par un ordinateur quantique, dont l’avènement futur nous impose de concevoir de nouveaux protocoles basés sur des problèmes différents. La cryptographie post-quantique a pour but de concevoir des protocoles reposant sur ces problèmes, a priori difficiles même pour un tel ordinateur. Parmi les approches envisagées, le décodage des codes correcteurs fait partie des problèmes intéressants. Alors que la cryptographie fondée sur ces codes s’appuie traditionnellement sur la métrique de Hamming, une alternative possible réside dans la métrique rang. Définie sur des extensions de corps finis, celle-ci présente des propriétés très différentes, et se caractérise par une complexité de décodage d’un code aléatoire qui croît rapidement avec la taille de celui-ci. Cela permet de concevoir des protocoles avec de plus petites tailles de clés qu’en métrique de Hamming, au prix de codes plus structurés, les rendant plus difficiles à masquer. Cette thèse contribue à l’étude et à la conception de tels protocoles. Dans un premier temps, on proposera des améliorations des schémas de chiffrement RQC et LRPC, en combinant l’approche multi-syndromes et l’utilisation d’erreurs structurées, deux techniques initialement introduites séparément mais qui peuvent être combinées et facilitent toutes deux le décodage, permettant ainsi d’obtenir de meilleurs paramètres. Elle présente ensuite le schéma de signature RYDE, présent au second tour du processus de standardisation du NIST pour les signatures post-quantiques, construit selon le paradigme MPC-in-the-Head, permettant d’avoir des paramètres compétitifs tout en reposant sur une instance générique du problème de décodage. Dans un second temps, la thèse explore des constructions basées sur les codes matriciels, dont le décodage correspond au problème MinRank. La perte de linéarité sur l’extension de corps rend ces codes moins structurés. Ainsi, une adaptation du chiffrement de McEliece aux codes matriciels est proposée, à notre connaissance premier schéma de chiffrement dont la sécurité repose sur le problème MinRank. Enfin, on proposera un schéma de signature de type hash-and-sign inspiré de CFS, permettant d’obtenir des signatures sous les 100 octets pour 143 bits de sécurité, tout en ayant une clé publique de taille convenable, le comportement asymptotique de celle-ci étant bien meilleur que celui de la taille de la clé de CFS.