Soutenance mémoire
La reconnaissance de codes correcteurs d’erreurs
Un premier problème qui a motivé cette thèse est la reconstruction de codes correcteurs d’erreurs. Ce problème se pose lorsque que nous voulons retrouver un code inconnu à partir de la seule connaissance de mots de code bruités ; le but étant de corriger ces mots mais aussi d’en corriger d’autres qui seront potentiellement émis ultérieurement. Si nous nous référons au schéma de transmission numérique de la figure 1, nous nous plaçons en sortie du démodulateur. Nous supposons donc que la démodulation a été correctement effectuée. Dans le cas où nous ne connaissons pas non plus les paramètres de modulation, il suffit généralement de tester exhaustivement toutes les techniques de démodulation connues jusqu’à trouver une information corrélée. En pratique, les codes rencontrés sont toujours des codes linéaires définis sur un corps fini ; c’est-à-dire qu’ils ont une structure d’espace vectoriel sur Fq où q est la taille du corps fini. Un code linéaire de longueur n et de dimension k sur Fq est donc un sous-espace vectoriel de dimension k de Fn q . Reconnaître de tels codes a été montré NP-complet par Valembois en 2001 [Val01], même sous l’hypothèse que la longueur et la dimension du code sont connues. Il sera donc nécessaire d’émettre des hypothèses supplémentaires, notamment sur la famille à laquelle appartient le code recherché. Pour de nombreuses familles de codes possédant une structure mathématique forte telle que les codes BCH, les codes de Reed-Solomon ou les codes de Reed-Muller, le problème de reconnaissance est essentiellement résolu. Cependant, pour d’autres familles, les solutions existantes sont insatisfaisantes.
Nous définissons les équations de parité d’un code linéaire comme étant les mots du code dual (c’est-à-dire les vecteurs de l’espace vectoriel dual). D’autre part, le nombre de positions non-nulles d’un vecteur est appelé poids de Hamming. Dans ce manuscrit, nous nous concentrons particulièrement sur la reconstruction de codes possédant des équations de parité de poids faible (borné par rapport à n). Parmi eux, nous avons les codes LDPC (Low-Density Parity-Check) mais aussi les codes convolutifs, les turbos-codes, les codes raptors, les codes fontaines ou encore les codes polaires. Dans nos travaux, nous avons développé une nouvelle technique de recherche d’équations de parité de petit poids dans un code. Celle-ci interpole et améliore les solutions existantes. Notre méthode exploite essentiellement deux idées. La première consiste à limiter la propagation des erreurs dans les mots bruités en réduisant le nombre d’opérations que nous effectuons sur ceux-ci. Pour cela, nous utilisons une élimination gaussienne partielle ou même l’algorithme BKW [BKW03]. Ce dernier permet de produire un grand nombre de zéros dans une matrice avec un nombre restreint d’opérations. La seconde idée est l’utilisation de nouvelles techniques pour résoudre le problème de recherche de presquecollisions. Ce problème consiste à rechercher tous les couples proches dans une liste d’éléments d’un espace métrique. Nous parlerons plus en détail de nos travaux sur ce problème un peu plus loin dans cette introduction. En outre, pour analyser notre algorithme de reconnaissance de codes, nous avons construit un outil permettant de dénombrer les équations de parité de poids donné dans un code. Pour n tendant vers l’infini, nous donnons également une expression asymptotique de nos énumérateurs de poids. Finalement, tous ces travaux ont été présentés lors du 10ème International Workshop on Coding and Cryptography en 2017 à St Petersbourg [CT17]. Une version longue de ce papier a été publiée dans le journal Designs, Codes and Cryptography en 2019 [CT19b].
Le décodage générique
Le problème de reconnaissance de codes LDPC s’avère être très proche de celui du décodage générique. Il consiste à effectuer une décodage avec la seule connaissance d’une base de l’espace vectoriel que forme le code. Dans la littérature, nous traitons généralement le problème dual équivalent : étant donnés une matrice H P F pn´kqˆn q , un vecteur s P F n´k q et un entier w P J0, nK, trouver un vecteur e P F n q qui contient au plus w positions non nulles et tel que HeJ “ s. Ce problème est aussi appelé décodage par syndrome. La sécurité de nombreux crypto-systèmes repose sur la difficulté de ce problème ; on parle alors de cryptographie fondée sur les codes correcteurs. Un des avantages de cette cryptographie est qu’elle produit de potentiels candidats pour protéger les systèmes d’information contre la menace des ordinateurs quantiques.
Depuis les années 60, de nombreuses méthodes ont été proposées pour résoudre le décodage générique. Dans les régimes difficiles, il demande un temps de calcul exponentiel en la longueur du code. Les différents algorithmes proposés depuis celui de Prange en 1962 [Pra62] n’ont pas changé la nature de la difficulté du problème. Toutefois, des avancées majeures ont permis de réduire significativement l’exposant de la complexité asymptotique. Parmi elles, nous pouvons citer les méthodes de Stern [Ste88] et de Dumer [Dum91] qui utilisent la recherche de collisions ou encore les méthodes MMT [MMT11] et BJMM [BJMM12] qui utilisent la technique des représentations de Howgrave-Graham et Joux [HJ10]. Les dernières avancées dans le domaine du décodage générique font toutes appel à des recherches de presque-collisions [MO15, BM17b, BM18].
Nous avons également contribué à améliorer le décodage générique. Dans le cas des espaces binaires de Hamming, nous avons réutilisé l’algorithme de Both et May [BM18] mais en remplaçant les étapes de recherche de presque-collisions par nos propres méthodes pour résoudre ce problème. Actuellement, la complexité record pour décoder génériquement un code binaire linéaire de longueur n dans le pire régime – c’est-à-dire pour la distance de décodage la plus difficile à atteindre et pour le pire rendement – est 2 0.08845np1`op1qq où 2 n op1q est sous-exponentiel en n mais super-polynomial. Nos travaux nous ont permis de diminuer l’exposant asymptotique de cette complexité : notre méthode permet en effet de résoudre la même instance du problème de décodage générique en un temps de l’ordre de 2 0.08821np1`op1qq . De plus, le surcoût 2 n op1q est ici inférieur à celui de Both et May ; nous soupçonnons même qu’il soit polynomial. Pour finir, nous avons généralisé l’algorithme Both-May aux espaces non-binaires. En instanciant cet algorithme avec nos méthodes de recherche de presque-collisions sur Fq, nous avons ainsi pu étendre nos améliorations sur le décodage générique à n’importe quels corps finis.
La recherche de presque-collisions
Par deux fois dans cette introduction, nous avons évoqué le problème de recherche de presque-collisions. Nous l’énonçons plus formellement comme suit : étant données deux listes L1 et L2 (éventuellement égales) d’éléments d’un espace métrique et une distance w, trouver les couples de L1 ˆ L2 à distance au plus w. Formulé ainsi, ce problème est très générique : nous ne précisons ni l’espace métrique, ni la façon dont les listes ont été générées. De plus, il en existe des variantes. Par exemple, l’une des listes peut être donnée sous forme de flux ; il s’agit alors de trouver dans l’autre liste les éléments proches de la requête courante fournie par ce flux. D’autres variantes consistent à rechercher non pas des couples proches mais le couple le plus proche.
Pour traiter ces problèmes de proximité, l’approche la plus connue est celle consistant à utiliser des fonctions de hachage localement sensibles ; c’est-à-dire des fonctions qui associent des mots proches à une même clé de hache avec une bonne probabilité [IM98]. De nombreuses solutions ont été proposées pour construire de telles fonctions. Certaines d’entre elles utilisent des décodages de codes correcteurs [GMO10, Dub10] : ce sont ces méthodes qui retiendront notre attention. Dans le cadre du décodage générique dans les espaces binaires, la méthode de May et Ozerov [MO15] pour la recherche de presque-collision a été une avancée importante. Elle a été adaptée aux espaces non-binaires par Hirose dans [Hir16]. En généralisant le problème de presque-collisions, nous touchons de nombreux domaines d’informatique qui vont au delà du problème de reconnaissance de codes ou de celui du décodage générique. Il permet notamment de traiter des problèmes majeurs de la cryptographie fondée sur les réseaux euclidiens. Cette dernière est une autre alternative envisageable pour la cryptographie résistante aux ordinateurs quantiques. Enfin, un problème analogue à la recherche de presque-collisions est celui qui consiste à rechercher des lointaines-collisions ; c’est-à-dire des couples d’éléments non pas proches mais le plus éloignés possible. Cette recherche peut être utilisée pour effectuer des décodages en gros poids. De tels décodages ont pour but de trouver le mot de code le plus éloigné d’un mot donné de l’espace ambiant. Ce problème a récemment trouvé une application dans une des premières signatures en cryptologie fondée sur les codes : WAVE [DST19].
|
Table des matières
Introduction
1 Quelques éléments de théorie de l’information
1.1 Les canaux de communication et les modèles d’erreur
1.1.1 L’entropie d’une source discrète
1.1.2 Les canaux discrets sans mémoire
1.1.3 Les canaux symétriques sur Fq et la fonction entropie q-aire
1.1.4 Les canaux binaires symétriques
1.1.5 Les canaux à effacement
1.1.6 Le modèle d’erreur
1.2 Généralités sur les codes correcteurs d’erreurs
1.2.1 Les codes en bloc linéaires
1.2.2 Les codes MDS
1.2.3 Les codes parfaits
1.2.4 La borne de Gilbert-Varshamov
1.3 Les codes LDPC
1.3.1 Les codes LDPC vs. les turbo-codes
1.3.2 Représentation des codes LDPC binaires
1.3.3 Les algorithmes de décodage à décisions dures
1.3.4 Les algorithmes de décodage à décisions souples
1.3.5 Régularité des codes LDPC
1.3.6 Les codes LDPC quasi-cycliques
1.3.7 Les codes LDPC avec une structure convolutive
1.4 Les codes U|U `V récursifs et les codes polaires
1.4.1 Définition d’un code U|U `V récursif
1.4.2 Modélisation des canaux associés à un code U|U `V récursif
1.4.3 Construction d’un code U|U `V récursif
1.4.4 Le cas particulier des codes polaires
1.4.5 Décodage des codes constituants
1.4.6 Décodage par annulation successive
1.4.7 Distorsion des décodages des codes U|U `V récursifs
1.4.8 Décodage en liste
2 Le décodage générique
2.1 Les enjeux de la cryptographie post-quantique
2.2 Une cryptographie basée sur les codes
2.3 Le décodage par syndrome
2.4 Le décodage par ensemble d’information
2.5 Le décodage par recherche de collisions
2.5.1 La méthode de Stern
2.5.2 Des presque-collisions dans la méthode de Stern
2.5.3 La méthode de Dumer
2.6 La technique des représentations
2.6.1 Définition et dénombrement des représentations
2.6.2 La méthode BJMM
2.6.3 Complexité de l’algorithme
2.7 La méthode de Both et May sur Fq
2.7.1 Description de l’algorithme
2.7.2 Choix des paramètres
2.7.3 Complexité de l’algorithme
2.8 Nos améliorations du décodage générique
2.8.1 Notre amélioration de la méthode Stern-May-Ozerov
2.8.2 Notre amélioration de la méthode Both-May
2.9 Le problème LPN
3 La reconnaissance de codes correcteurs d’erreurs
3.1 La méthode Tixier-Tillich
3.1.1 Une méthode inspirée du décodage ISD de Dumer
3.1.2 À propos de l’élimination gaussienne partielle
3.1.3 Complexité de la méthode Tixier-Tillich
3.1.4 Accélération de la reconnaissance de codes LDPC
3.2 Deux méthodes classiques
3.2.1 La méthode de Cluzeau et Finiasz
3.2.2 La méthode de Sicot, Houcke et Barbier
3.3 Reconnaitre un code LDPC par élimination gaussienne partielle
3.3.1 Analyse de la méthode
3.3.2 Quelques résultats numériques
3.4 Reconnaitre un code en résolvant LPN
4 Énumérateur de poids des équations de parité d’un code LDPC
4.1 Polynôme énumérateur de poids d’un code
4.2 Énumérateur de poids d’un code linéaire aléatoire
4.3 Théorème de MacWilliams
4.4 Énumérateur de poids d’un code LDPC
4.5 Énumérateur de poids du dual d’un code LDPC
5 La recherche de presque-collisions
5.1 La recherche de voisins proches
5.1.1 La recherche du plus proche voisin
5.1.2 Le fléau de la dimension
5.1.3 Un voisin proche plutôt que le plus proche
5.2 La recherche de presque-collisions
5.2.1 Définition du problème
5.2.2 Les presque-collisions en cryptographie
5.2.3 Les modèles de proximité
5.3 L’approche des fonctions localement sensibles
5.3.1 Définition d’une famille de fonctions LSH
5.3.2 L’algorithme LSH générique
Conclusion
Télécharger le rapport complet
