Analyse des algorithmes de décodage des codes QC-MDPC

Les codes QC-MDPC permettent la conception du cryptosystème de McEliece avec des clés et une sécurité qui réduit à l’évidence les problèmes de décodage pour les codes quasi-cycliques. En particulier, ces codes sont parmi les plus prometteurs qui sont proposés à l’appel du NIST pour la normalisation de la cryptographie post-quantique. ). Ce qui a permis l’attaque de récupération de clés de Guo, Johansson et Stankovski qui exploite une petite corrélation entre les messages erronés et la clé secrète du cryptosystème de McEliece [42]. Cependant, cette attaque semble ne pas avoir d’incidence sur l’établissement interactif de communications sécurisées (le protocole TLS par exemple), mais l’utilisation de clés publiques statiques pour des applications asynchrones (les courriers électroniques par exemple) est rendue dangereuse.

Optimisation de l’algorithme Bit-flipping

L’algorithme Bit-flipping a été décrit dans le chapitre 2. Cependant, il est nécessaire de rappeler de manière brève le fonctionnement de l’algorithme. Ainsi, pour un mot de code 𝑥 ∈ 𝔽Le nombre d’équations de contrôle de parité insatisfaites est égal au nombre de bits partagés dans une ligne de la matrice de contrôle de parité 𝐻 et du syndrome 𝑠. A noté que le syndrome ne dépend, par définition, que de l’erreur 𝑒 qui est ajoutée à un mot de code 𝑐 ∶ Les décodeurs Bit-flipping dans la littérature recalculent le syndrome après chaque itération pour décider si le décodage a réussi ou non. Le coût d’un seul calcul du syndrome peut être estimé à environ deux fois le coût d’un encodage dans le cas des codes QC-MDPC avec 𝑛Les auteurs de [44] proposent une optimisation qui peut être appliquée à tous les décodeurs bit- flipping, basée sur l’observation suivante : si le nombre d’équations de contrôle de parité non satisfaites dépasse un seuil qu’on notera 𝑏, le bit correspondant dans le texte chiffré est inversé et le syndrome change. Soulignons que le syndrome ne change pas arbitrairement, mais le nouveau syndrome est égal à l’ancien syndrome accumulé avec la ligne ℎEn gardant la trace des bits qui sont retournés et en mettant à jour le syndrome en conséquence, le recalcule du syndrome peut être omis. Comme seuls quelques bits sont inversés à chaque itération lors du décodage, la mise à jour du syndrome nécessite beaucoup moins d’ajouts qu’un calcul de syndrome ordinaire.

Il y a deux façons d’appliquer le calcul du syndrome pour les optimisations du paragraphe précédent. L’une d’elles consiste à stocker toutes les modifications du syndrome dans un registre séparé et d’ajouter les modifications à la fin d’une itération de décodage au syndrome. Ainsi, le calcul du syndrome est accéléré mais le comportement du décodage reste inchangé. L’autre possibilité est d’appliquer directement les changements au syndrome à chaque fois qu’un bit du texte chiffré est retourné. Cela accélère également le calcul du syndrome mais affecte également le comportement du décodage puisque le syndrome modifié est utilisé pour déterminer les équations de contrôle de parité non satisfaites de bits de texte chiffré suivants.

Les variantes de l’algorithme Bit-flipping

Les algorithmes itératifs bit-flipping ont un taux d’échec de décodage beaucoup plus élevé lorsqu’ils sont utilisés pour décoder les codes MDPC que ceux des équivalents LDPC. Ceci est dû au fait que la matrice de contrôle de parité d’un code LDPC est sensiblement plus clairsemée qu’une matrice correspondante pour le code MDPC. Autrement dit chaque ligne de la matrice pour le code MDPC contient un plus grand nombre d’entrées non nulles et donc le nombre de bits inclus dans le calcul de chaque bit du syndrome est considérablement augmenté. Raison pour laquelle il est plus difficile de décider si un bit est erroné ou non. Dans la construction originale de Gallager, une seule décision était prise par bit en une itération, et en inversant un bit qui n’est pas en erreur, la probabilité d’une défaillance de décodage est plus élevée.

La variante Black-Gray [45] de l’algorithme Bit-flipping utilise plusieurs étapes dans une itération de décodage unique afin de réduire la probabilité de retourner les bits inutiles et réduire le taux d’échec. Il utilise deux seuils prédéfinis 𝛿 et 𝑑 pour trier les bits avec un nombre élevé d’équations de contrôles de parité insatisfaisants en deux ensembles : l’ensemble noir et l’ensemble gris. ). L’algorithme comporte trois principales étapes. L’étape I consiste à effectuer une itération de l’algorithme Bit-flipping et marquer les bits inversés avec des étiquettes B pour Black (noire) et G pour Gray (grise). L’étape II consiste à déverrouiller les bits d’erreur noirs qui atteignent un certain seuil. La dernière étape, l’étape III, consiste aussi à déverrouiller les bits d’erreur gris qui atteignent un certain seuil.

L’algorithme fonctionne comme suit : les bits avec un nombre maximum d’équations de contrôles de parité non satisfaites sont classés comme des bits Black (noirs) et retournés immédiatement. Les bits dont le nombre d’équations de contrôles parité non satisfaits s’écartant du maximum d’un nombre inférieur au seuil 𝛿, sont classées comme des bits Gray (gris), mais ne sont pas retournées. Après la boucle initiale, le syndrome et le nombre d’équations de contrôles de parité non satisfaits sont recalculés pour chaque bit. Ensuite, chaque bit dans les deux ensembles de Black et de Gray sont analysés à nouveau : si le nombre d’équations de contrôles de parité non satisfaites dépasse un seuil défini par le deuxième paramètre 𝑑, les bits noirs qui dépassent ce seuil sont ramenés à leur état initial et les bits gris sont retournés. Après chaque étape, le nombre d’équations de contrôles de parité non satisfaisants est mis à jour en conséquence .