Si vous avez déjà envoyé un message texte, lu un CD ou stocké un fichier dans le cloud, vous avez bénéficié d'une correction d'erreur. Cette idée révolutionnaire remonte aux années 1940, lorsque les chercheurs ont réalisé pour la première fois qu’il était possible de réécrire n’importe quel message sous une forme permettant d’inverser facilement la corruption ultérieure.

Au fil des années, les chercheurs ont développé de nombreux systèmes ingénieux, appelés codes correcteurs d’erreurs, qui codent les données de différentes manières et utilisent différentes procédures pour corriger les erreurs. Mais pour les informaticiens théoriques, rares sont ceux qui sont aussi convaincants que les codes dits corrigibles localement. Ces codes ont deux propriétés simultanées qui semblent presque contradictoires : toute erreur peut être corrigée en lisant les données codées à quelques endroits seulement, mais aucun attaquant ne peut déjouer cette procédure de correction en falsifiant sélectivement le code. C’est comme si vous pouviez récupérer n’importe quelle page arrachée d’un livre en jetant simplement un coup d’œil à quelques autres.

"C'est un phénomène assez magique", a déclaré Tom Gur, informaticien à l'Université de Cambridge. "A priori, il n'est pas évident qu'un tel objet mathématique puisse exister."

Mais cette magie a un coût élevé. Les seuls exemples connus de codes corrigibles localement sont extrêmement inefficaces : le codage de n’importe quel message le rend également exponentiellement plus long. Des livres entiers codés de cette manière seraient beaucoup trop lourds à manier.

Les informaticiens se demandent depuis longtemps s’il était possible de meilleurs codes corrigibles localement. Ils se sont particulièrement concentrés sur les codes qui n’utilisent que trois requêtes pour corriger toute erreur, en espérant que cette restriction sévère pourrait rendre ces codes plus faciles à comprendre. Mais même ce simple cas a déconcerté les chercheurs pendant plus de 20 ans.

Maintenant l'informaticien Pravesh Kothari de l'Université Carnegie Mellon et son étudiant diplômé Peter Manohar avoir enfin prouvé qu'il est impossible de créer un code à trois requêtes corrigible localement qui évite ce coût exponentiel. Il s’agit peut-être d’un résultat négatif, mais tout ce qui clarifie les limites de la correction d’erreurs enthousiasme les chercheurs, notamment parce que les mathématiques des codes corrigibles localement surgissent dans des domaines très éloignés de la communication.

"Ce résultat est incroyable", a déclaré Shubhangi Saraf, informaticien à l'Université de Toronto. "C'est une énorme avancée."

La force du nombre

Pour comprendre la correction d’erreurs, imaginez les données que vous souhaitez protéger sous la forme d’une séquence de bits, ou de 0 et de 1. Une erreur, dans ce modèle, peut être toute transformation indésirable d’un 0 en un 1 ou vice versa, que ce soit en raison d’une fluctuation aléatoire ou d’une falsification délibérée.

Supposons que vous souhaitiez envoyer un message à un ami, mais que vous craigniez que des erreurs puissent en modifier le sens. Une stratégie simple consiste à remplacer chaque 0 de votre message par 000 et chaque 1 par 111. Si votre ami voit une partie du message qui ne contient pas trois bits identiques d'affilée, il saura qu'une erreur s'est produite. Et si les erreurs sont aléatoires et relativement rares, alors toute chaîne de 110 est beaucoup plus susceptible d'être un 111 corrompu qu'un 000 corrompu. Un simple vote majoritaire au sein de chaque triplet suffira à corriger la plupart des erreurs.

Ce schéma, appelé code de répétition, a le mérite de la simplicité, mais n'a rien d'autre à recommander. D’une part, il faut tripler la longueur de chaque message juste pour traiter des erreurs relativement peu fréquentes, et s’il y a une bonne chance qu’il y ait deux erreurs adjacentes, nous aurons besoin d’encore plus de redondance. Pire encore, cela devient vite inutile si les erreurs ne sont pas aléatoires, comme lorsque des attaquants tentent activement de saboter le code. Dans le code de répétition, toutes les informations nécessaires pour corriger un bit donné sont stockées dans quelques autres bits seulement, le rendant vulnérable à une attaque ciblée.

Heureusement, de nombreux codes correcteurs d’erreurs s’en sortent mieux. Un exemple célèbre, appelé le Code Reed-Salomon, fonctionne en transformant les messages en polynômes – des expressions mathématiques comme x² + 3x + 2 qui sont constitués de différents termes additionnés, chacun avec une variable (comme x) élevé à une puissance différente. Encoder un message à l'aide d'un code de Reed-Solomon implique de construire un polynôme avec un terme pour chaque caractère du message, puis de tracer le polynôme sous forme de courbe sur un graphique et de stocker les coordonnées des points qui se trouvent sur la courbe (en prenant au moins un autre point que le nombre de caractères). Les erreurs peuvent faire sortir quelques-uns de ces points de la courbe, mais s’il n’y a pas trop d’erreurs, une seule courbe polynomiale passera par la plupart des points. Cette courbe correspond presque certainement au vrai message.

Les codes Reed-Solomon sont hyperefficaces : il vous suffit de stocker quelques points supplémentaires pour corriger les erreurs, de sorte que tout message codé n'est que légèrement plus long que l'original. Ils sont également moins vulnérables au type de perturbation ciblée qui entraînerait un désastre pour le code de répétition, car les informations utilisées pour corriger une erreur n’importe où sont réparties dans l’ensemble du message codé.

Penser globalement agir localement

La force du code Reed-Solomon vient de l’interdépendance. Mais précisément à cause de cette interconnexion, il n’existe aucun moyen de corriger une seule erreur dans un message codé sans lire l’intégralité du message. Cela ne semble pas être un problème dans le contexte de la communication : si vous envoyez un message, vous souhaitez probablement que le destinataire le lise en entier. Mais cela peut constituer un handicap en matière de stockage de données – une autre application majeure de la correction d’erreurs.

Prenons l’exemple d’une entreprise qui stocke les e-mails des utilisateurs dans le cloud, c’est-à-dire sur une vaste gamme de serveurs. Vous pouvez considérer l’ensemble de votre collection d’e-mails comme un seul long message. Supposons maintenant qu'un serveur tombe en panne. Avec un code Reed-Solomon, vous devrez effectuer un calcul massif impliquant toutes les données codées pour récupérer vos e-mails sur ce serveur perdu. "Il faudrait tout regarder", a déclaré Zeev Dvir, informaticien à l'Université de Princeton. "Cela pourrait représenter des milliards et des milliards d'e-mails, cela pourrait prendre très longtemps."

Les chercheurs utilisent le terme « local » pour décrire des codes qui n'utilisent qu'une fraction du message codé pour repérer les erreurs ou les corriger. Le simple code de répétition a quelque chose de ce caractère local, mais c’est précisément ce qui le rend si vulnérable à la falsification. En revanche, un code corrigible localement offre le meilleur des deux mondes : il peut corriger une erreur en tout temps avec seulement quelques requêtes, le tout sans perdre l'interconnectivité qui rend les codes Reed-Solomon si résilients.

"C'est une notion très stricte", a déclaré Kothari.

Les exemples les plus célèbres de codes corrigibles localement sont des versions d'un vénérable code correcteur d'erreurs inventé en 1954 par les mathématiciens. David Müller et les Irving Reed (qui a également aidé à développer les codes Reed-Solomon). Comme les codes Reed-Solomon, les codes Reed-Muller utilisent des polynômes avec de nombreux termes additionnés pour coder des messages longs.

Les polynômes utilisés dans les codes Reed-Solomon impliquent une seule variable, x, donc la seule façon d'ajouter plus de termes est d'utiliser des puissances de x. Il en résulte une courbe comportant de nombreux mouvements qui ne peuvent être identifiés qu'en examinant de nombreux points. Les codes Reed-Muller utilisent à la place des polynômes dans lesquels chaque terme peut contenir plusieurs variables multipliées ensemble. Plus de variables signifie plus de façons de les combiner, ce qui offre à son tour un moyen d'augmenter le nombre de termes polynomiaux sans élever aucune variable individuelle à des puissances aussi élevées.

Les codes Reed-Muller sont très flexibles. Vous pouvez coder des messages plus longs en augmentant la puissance la plus élevée qui apparaît dans le polynôme, en augmentant le nombre de variables, ou les deux. Pour rendre un code Reed-Muller corrigible localement, il vous suffit de limiter la puissance maximale de chaque variable à une petite valeur constante et de gérer des messages plus longs en augmentant uniquement le nombre de variables.

Pour un code corrigible localement à trois requêtes en particulier, cette puissance maximale est fixée à 2. Ensuite, en ce qui concerne chaque variable individuelle, le polynôme codant le message trace une simple parabole. Pour déterminer la forme exacte de cette parabole, il vous suffit d’examiner la courbe en trois points. De plus, avec de nombreuses variables, il existe de nombreuses paraboles de ce type, dont chacune peut être utilisée pour corriger des erreurs. C’est ce qui rend les codes Reed-Muller si résistants.

Malheureusement, le code de Reed-Muller présente un sérieux inconvénient : le nombre de bits requis pour coder un message augmente de façon exponentielle avec le nombre de variables. Si vous souhaitez un code très local qui corrige les erreurs avec seulement une poignée de requêtes, vous aurez besoin de beaucoup de variables pour les messages longs, et le code de Reed-Muller deviendra vite inutile en pratique.

"L'exponentielle dans ce cas est très mauvaise", a déclaré Dvir. Mais est-ce inévitable ?

Corrigable ou décodable ?

Alors que les informaticiens essayaient sans succès de trouver des codes corrigibles localement plus efficaces, ils ont commencé à soupçonner que de tels codes n’étaient pas du tout possibles. En 2003, deux chercheurs prouvé qu'il n'y a aucun moyen de battre le code Reed-Muller en utilisant seulement deux requêtes. Mais c’est tout ce que quiconque peut obtenir.

"Une fois que vous passez à trois, nos connaissances deviennent très sommaires", a déclaré Kothari.

La percée suivante n’a fait que compliquer encore davantage les choses. Dans deux articles publiés dans 2008 et les 2009, les informaticiens Sergey Yekhanin et Klim Efremenko ont montré comment construire des codes à trois requêtes plus efficaces que les codes de Reed-Muller, mais ces codes n'étaient pas tout à fait corrigibles localement. Au lieu de cela, ils avaient une propriété subtilement différente appelée décodabilité locale.

Pour comprendre la différence, imaginons à nouveau un fournisseur de stockage cloud qui combine les données des utilisateurs en un seul long message et les protège à l’aide d’un code correcteur d’erreurs. Les codes corrigibles localement et les codes décodables localement peuvent corriger une erreur dans n'importe quel bit du message d'origine avec seulement quelques requêtes.

Mais chaque code de correction d’erreurs nécessite également des bits supplémentaires qui ne figuraient pas dans le message d’origine – c’est pourquoi l’encodage d’un message le rend plus long. Les deux types de codes diffèrent dans la manière dont ils traitent ces bits supplémentaires. Les codes décodables localement ne font aucune promesse quant au nombre de requêtes nécessaires pour corriger les erreurs dans ces bits. Mais dans un code corrigible localement, une erreur dans l’un des bits supplémentaires peut être corrigée exactement de la même manière qu’une erreur dans n’importe quel bit du message d’origine.

"Tout ce que vous stockez, qu'il s'agisse des données originales des utilisateurs ou des informations de redondance et de contrôle, tout cela peut être corrigé localement", a déclaré Madhu Soudan, informaticien à l'Université Harvard.

Bien que différentes en principe, la corrigibilité locale et la décodabilité locale semblaient toujours interchangeables dans la pratique avant 2008 : chaque code connu localement décodable était également corrigible localement. La découverte de Yekhanin et Efremenko a soulevé la possibilité d’une différence fondamentale entre les deux conditions. Ou peut-être était-il possible de modifier les codes d’Ekhanin et d’Efremenko pour les rendre corrigibles localement. Cela mettrait à nouveau les deux conditions sur un pied d'égalité, mais cela signifierait également que les chercheurs se sont trompés sur l'efficacité des codes corrigibles localement à trois requêtes. Quoi qu’il en soit, les idées reçues devraient changer.

Logique d’emprunt

Kothari et Manohar ont finalement résolu cette tension en adaptant une technique issue d'un autre domaine de l'informatique : l'étude des problèmes dits de satisfaction de contraintes. Essayer de coordonner les projets de dîner avec un groupe d’amis est en quelque sorte un problème de satisfaction des contraintes. Tout le monde a des choix qu’il acceptera et des choix sur lesquels il mettra son veto. Votre travail consiste soit à trouver un plan qui satisfasse tout le monde, soit, s'il n'existe pas de tel plan, à le trouver le plus tôt possible.

Il existe une asymétrie inhérente entre ces deux résultats possibles. Une solution acceptable n’est peut-être pas facile à trouver, mais une fois que vous l’avez trouvée, il est facile de convaincre quelqu’un d’autre qu’elle fonctionnera. Mais même si vous savez que le problème est réellement « insatisfaisant », il se peut qu’il n’y ait pas d’exemple qui en fournisse la preuve.

En 2021, Kothari et Manohar, avec Venkatesan Guruswami de l'Université de Californie à Berkeley, ont réalisé une percée majeure dans l'étude des problèmes de satisfaction de contraintes en utilisant une nouvelle technique théorique pour identifier ces cas insatisfiables délicats. Ils soupçonnaient que la nouvelle méthode serait également un outil puissant pour résoudre d’autres problèmes, et Omar Alrabiah, étudiant diplômé de Guruswami, a suggéré d’examiner des codes à trois requêtes décodables localement.

"C'était un clou avec un marteau à la main, pour ainsi dire", a déclaré Kothari.

Les résultats surprenants de Yekhanin et Efremenko avaient montré que les codes à trois requêtes décodables localement pouvaient être plus efficaces que les codes de Reed-Muller. Mais leurs codes étaient-ils les meilleurs possibles, ou les codes à trois requêtes décodables localement pourraient-ils devenir encore plus efficaces ? Kothari, Manohar, Guruswami et Alrabiah pensaient que leur nouvelle technique pourrait prouver les limites de l'efficacité de ces codes. Leur plan était de construire une formule logique englobant la structure de tous les codes possibles à trois requêtes décodables localement d'une taille donnée, et de la prouver insatisfaisante, montrant ainsi qu'un tel code ne pouvait exister.

Les quatre chercheurs ont fait un premier pas dans cette direction en 2022, en établissant un nouvelle limite sur l'efficacité maximale des codes à trois requêtes décodables localement. Le résultat allait bien au-delà de ce que les chercheurs avaient pu obtenir avec d’autres techniques, mais il n’excluait pas tous les codes plus efficaces que ceux de Yekhanin et Efremenko.

Kothari et Manohar soupçonnaient qu'ils pourraient aller plus loin. Mais les progrès ont été bloqués jusqu'à ce que Manohar ait noté un rapide calcul indiquant que la technique pourrait fonctionner encore mieux pour les codes corrigibles localement que pour ceux décodables localement.

Quelques mois plus tard, après de nombreux faux départs qui leur faisaient craindre d’avoir été trop optimistes, la technique tient enfin ses promesses. Kothari et Manohar ont prouvé que, comme les chercheurs l'avaient soupçonné, il est impossible qu'un code corrigible localement à trois requêtes fonctionne sensiblement mieux que les codes de Reed-Muller. Cette mise à l'échelle exponentielle est une limitation fondamentale. Leur résultat a également été une démonstration spectaculaire que la corrigibilité locale et la décodabilité locale, bien que superficiellement similaires, diffèrent réellement à un niveau fondamental : la dernière est sans équivoque plus facile à réaliser que la première.

Kothari et Manohar espèrent désormais étendre leurs techniques pour étudier les codes autorisés à effectuer plus de trois requêtes, car on en sait très peu à leur sujet actuellement. Et les progrès de la théorie de la correction d’erreurs ont souvent des implications dans d’autres domaines apparemment sans rapport. En particulier, les codes corrigibles localement font des apparitions surprises partout, du problème de recherches dans des bases de données privées en cryptographie aux preuves de théorèmes de combinatoire. Il est trop tôt pour dire quel impact la technique de Kothari et Manohar aura sur ces différents domaines, mais les chercheurs se sentent optimistes.

"Il y a une très belle nouvelle idée ici", a déclaré Dvir. "Je pense qu'il y a beaucoup de potentiel."