Description
Date depot: 1 janvier 1900
Titre: Cryptographie post-quantique : étude du décodage des codes QC-MDPC
Directeur de thèse:
Nicolas SENDRIER (Inria-Paris (ED-130))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
{{{Le cryptosystème de McEliece : chiffrer avec des codes correcteurs d'erreurs}}}
Le chiffrement consiste à transformer le texte clair en un mot d'un code linéaire (de façon publique et réversible) puis à ajouter des erreurs aléatoires. L'utilisateur légitime connaît l'algorithme de décodage et peut retirer les erreurs. L'adversaire qui ignore le secret (l'algorithme de décodage) doit résoudre un problème algorithmique dont la résolution est hors de portée.
{{La variante QC-MDPC-McEliece.}} Récemment, une variante quasi-cyclique du système de McEliece a été proposée utilisant les codes MPDC ({Moderate Density Parity Check}) [5]. Cette variante propose de bonnes garanties de sécurité, y compris contre un adversaire quantique, tout en offrant des clés publiques de taille raisonnable (de l'ordre de 10 kilobits contre 2 megabits pour un McEliece « classique », soit un facteur 200, à sécurité égale).
{{{Sujet : étude du décodage des codes QC-MDPC}}}
Les systèmes à clé publique basés sur les codes QC-MDPC feront probablement partie des candidats à l'appel du NIST (cf. {{Enjeux}} plus bas). Deux types de primitives (selon la nomemclature de l'appel du NIST) présentent un intérêt, le chiffrement ({public-key encryption}) et l'échange de clé ({key establishment}). La première est plus générale, la seconde est moins exigeante en terme de sécurité. En particulier, les mécanismes d'échange de clé ne nécessitent pas une variante « sans échec » (cf. plus bas).
{{Le décodage.}} Le décodage des codes MDPC dérive naturellement de celui des codes LDPC ({Low Density Parity Check}) qui sont très utilisés en télécommunication pour la protection contre le bruit. Le décodeur le plus élémentaire est le « bit flipping ». L'étude de cet algorithme pour les codes MDPC dans le contexte de la cryptographie a été commencée dans une thèse soutenue récemment [1] qui constituera l'un des points de départ de l'étude.
{{Améliorations de l'algorithme de décodage.}} Le decodage « bit flipping » est à décision {dure}, c'est-à-dire qu'au cours du calcul chaque coordonnée de vecteur vaudra 0 ou 1. L'un des intêrets de QC-MDPC-McEliece, avec le décodage dur, est d'être adapté à des implémentations embarquées [3]. Toutefois, il existe d'autres algorithmes de décodage itératifs, à décision {souple} (algorithmes « min-max » ou « sum-product »), beaucoup plus performants en terme de correction d'erreurs, dans lesquels les valeurs 0 ou 1 sont accompagnées d'une information de fiabilité, sous la forme d'un entier ou même d'un nombre flottant. Ces algorithmes ont une logique plus complexe, de plus l'arithmétique nécessaire à la mise à jour des fiabilités entraîne un surcoût conséquent.
De nombreux intermédiaires sont possibles entre le décodage dur et le décodage souple. Au cours du calcul on peut choisir de ne conserver qu'une partie des informations de fiabilité. L'objectif est d'obtenir le meilleur compromis entre les performances de correction du décodeur et son coût algorithmique. Idéalement, obtenir un algorithme suffisamment simple pour une implémentation embarquée en s'approchant des performances d'un décodeur à décision souple.
{{Estimation de la probabilité d'échec et variantes « sans échec » du décodage.}} Le décodage « bit flipping » est itératif, selon les paramètres le nombre moyen d'itérations peut varier. Pour un code donné le nombre d'itérations peut varier selon l'instance, et l'algorithme peut échouer dans certains cas. Cette situation doit être évitée car il a été montré très récemment [2] qu'il existait une corrélation entre la clé secrète et les vecteurs d'erreur provoquant un échec du décodage. Cette corrélation peut-être exploitée par un attaquant ayant accès à un dispositif de déchiffrement utilisant une clé fixe donnée et auquel il soumettra un grand nombre de cryptogramme.
Pour lutter contre cette attaque, il faut réduire la probabilité d'échec du décodeur à une valeur négligeable. Pour atteindre cet objectif sans réduire la sécurité du schéma il suffira d'augmenter la taille de bloc. L'objectif, en s'appuyant sur [1], consistera à trouver des bornes à la probabilité d'échec puis d'en déduire la valeurs des paramètres permettant d'amener cette probabilité à une valeur suffisamment faible.
-# Julia Chaulet. « Étude de cryptosystèmes à clé publique basés sur les codes MDPC quasi-cycliques ». Thèse de doctorat, University Pierre et Marie Curie, mars 2017.
-# Qian Guo, Thomas Johansson et Paul Stankovski. « A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors ». Dans Jung Hee Cheon et Tsuyoshi Takagi, éditeurs, Advances in Cryptology - ASIACRYPT 2016, volume 10031 de LNCS, pages 789–818. Springer, décembre 2016.
-# Stefan Heyse, Ingo von Maurich et Tim Güneysu. « Smaller Keys for Code-Based Cryptography: QC-MDPC McEliece Implementations on Embedded Devices ». Dans Guido Bertoni et Jean-Sébastien Coron, éditeurs, CHES, volume 8086 de LNCS, pages 273–292. Springer, 2013.
-# R.
Doctorant.e: Vasseur Valentin