En 1994, l'informaticien Peter Shor découvert que si les ordinateurs quantiques étaient inventés, ils décimeraient une grande partie de l'infrastructure utilisée pour protéger les informations partagées en ligne. Cette possibilité effrayante a poussé les chercheurs à produire de nouveaux schémas de cryptage «post-quantique», pour éviter que le plus d'informations possible ne tombent entre les mains de pirates quantiques.

Plus tôt cette année, l'Institut national des normes et de la technologie révélé quatre finalistes dans sa recherche d'une norme de cryptographie post-quantique. Trois d'entre eux utilisent la «cryptographie en réseau» - un schéma inspiré des réseaux, des arrangements réguliers de points dans l'espace.

La cryptographie en réseau et d'autres possibilités post-quantiques diffèrent des normes actuelles de manière cruciale. Mais ils reposent tous sur l'asymétrie mathématique. La sécurité de nombreux systèmes de cryptographie actuels est basée sur la multiplication et la factorisation : n'importe quel ordinateur peut rapidement multiplier deux nombres, mais cela pourrait prendre des siècles pour factoriser un nombre cryptographiquement grand dans ses constituants premiers. Cette asymétrie rend les secrets faciles à encoder mais difficiles à décoder.

Ce que Shor a révélé dans son algorithme de 1994, c'est qu'une bizarrerie de factorisation le rend vulnérable aux attaques des ordinateurs quantiques. "C'est une chose très spécifique et spéciale que l'ordinateur quantique peut faire", a déclaré Catherine Stange, mathématicien à l'Université du Colorado, Boulder. Ainsi, après Shor, les cryptographes ont eu un nouveau travail : trouver un nouvel ensemble d'opérations mathématiques faciles à effectuer mais presque impossibles à annuler.

La cryptographie en réseau est l'une des tentatives les plus réussies à ce jour. Développé à l'origine dans les années 1990, il repose sur la difficulté de rétro-ingénierie des sommes de points.

Voici une façon de décrire la cryptographie en treillis : imaginez que votre ami a un treillis, qui est juste un tas de points dans un motif régulier et répétitif sur tout le plan. Votre ami veut que vous nommiez 10 de ces points. Mais il est difficile et il ne dessinera pas tout le treillis. Au lieu de cela, il n'énumère que deux points - le premier avec un x-valeur de 101 et un y-valeur de 19, l'autre de coordonnées [235, 44].

Heureusement, il est facile de trouver de nouveaux points sur un treillis, car lorsque vous additionnez et soustrayez deux points quelconques sur un treillis, vous obtenez un troisième point dans le même treillis. Donc, tout ce que vous avez à faire est d'additionner les points que votre ami vous a donnés, ou de les multiplier par des nombres entiers, puis de les additionner, ou une combinaison des deux. Faites cela de huit manières différentes et vous pourrez répondre à la question de votre ami.

Mais votre ami n'est toujours pas satisfait. Il vous donne les deux mêmes points de départ, puis vous demande si vous pouvez trouver un point proche de [0, 0] sur le même réseau. Pour répondre correctement à cette question, vous devez trouver la combinaison de [101, 19] et [235, 44] qui vous rapproche de [0, 0]. Ce problème est beaucoup plus difficile que le premier, et vous finirez probablement par deviner et vérifier pour obtenir la réponse. Cette asymétrie est ce qui sous-tend la cryptographie en réseau.

Si vous souhaitez réellement utiliser la cryptographie en treillis pour partager des informations, procédez comme suit. Imaginez qu'un ami (un plus gentil !) veuille vous envoyer un message sécurisé. Vous commencez avec une grille carrée de nombres. Disons qu'il a deux lignes et deux colonnes, et ressemble à ceci :

Maintenant, vous venez avec une "clé" privée que vous seul connaissez. Dans cet exemple, supposons que votre clé privée ne soit composée que de deux nombres secrets : 3 et -2. Vous multipliez les nombres de la première colonne par 3 et ceux de la deuxième colonne par -2. Additionnez les résultats de chaque ligne pour obtenir une troisième colonne avec deux entrées.

Collez la nouvelle colonne au bout de votre grille. Cette nouvelle grille à trois colonnes est votre clé publique. Partagez-le librement !

(Un scénario réel sera un peu plus compliqué. Pour empêcher les pirates de décoder votre clé privée, vous devez ajouter un peu de bruit aléatoire dans votre dernière colonne. Mais ici, nous allons ignorer cette étape par souci de simplicité. )

Maintenant, votre ami utilisera la clé publique pour vous envoyer un message. Elle pense à deux nombres secrets : 2 et 0. Elle multiplie les nombres de la première rangée par 2 et ceux de la deuxième rangée par 0. Elle additionne ensuite les résultats de chaque colonne pour obtenir une troisième rangée.

Elle attache maintenant la nouvelle ligne au bas de la grille et vous la renvoie. (Encore une fois, dans un système réel, elle aurait besoin d'ajouter du bruit à sa ligne.)

Vous allez maintenant lire le message. Pour ce faire, vous vérifiez si la dernière ligne de votre ami est correcte. Appliquez votre propre clé privée aux deux premières entrées de sa ligne. Le résultat doit correspondre à la dernière entrée.

Votre ami peut également choisir de vous envoyer une ligne avec un mauvais numéro dans la dernière colonne. Elle sait que ce nombre ne correspondra pas à vos calculs.

Si votre ami envoie une ligne où le dernier numéro est correct, vous l'interpréterez comme un 0. S'il envoie une ligne où le numéro est incorrect, vous l'interpréterez comme un 1. La ligne encode donc un seul bit : 0 ou 1.

Notez qu'un attaquant extérieur n'aura accès ni à votre clé privée ni à celle de votre ami. Sans ceux-ci, l'attaquant n'aura aucune idée si le nombre final est correct ou non.

En pratique, vous aimeriez envoyer des messages plus longs qu'un bit. Ainsi, les personnes qui souhaitent recevoir, par exemple, un message de 100 bits généreront 100 nouvelles colonnes au lieu d'une seule. Ensuite, l'expéditeur du message créera une nouvelle ligne unique, modifiant les 100 dernières entrées pour encoder soit un 0 soit un 1 pour chaque entrée.

Si la cryptographie en treillis est réellement mise en œuvre, elle aura d'innombrables nuances non couvertes dans ce scénario. Par exemple, si vous voulez que le message soit vraiment à l'abri des regards indiscrets, la matrice doit avoir un nombre impensable d'entrées, ce qui rend l'ensemble si lourd qu'il ne vaut pas la peine de l'utiliser. Pour contourner ce problème, les chercheurs utilisent des matrices avec des symétries utiles qui peuvent réduire le nombre de paramètres. Au-delà de cela, il existe toute une suite de réglages qui peuvent être appliqués au problème lui-même, à la façon dont les erreurs sont incorporées, et plus encore.

Bien sûr, il est toujours possible que quelqu'un trouve une faille fatale dans la cryptographie en treillis, tout comme Shor l'a fait pour l'affacturage. Rien ne garantit qu'un schéma cryptographique particulier fonctionnera face à une éventuelle attaque. La cryptographie fonctionne jusqu'à ce qu'elle soit fissurée. En effet, plus tôt cet été un schéma de cryptographie post-quantique prometteur a été fissuré en utilisant non pas un ordinateur quantique, mais un ordinateur portable ordinaire. Pour Stange, l'ensemble du projet crée un paradoxe inconfortable : "Ce que je trouve si étonnant dans la cryptographie, c'est que nous avons construit cette infrastructure pour la race humaine sur la ferme conviction que nos capacités en tant qu'humains sont limitées", a-t-elle déclaré. "C'est tellement en arrière."

Correction: 9 novembre 2022
La version originale de cet article disait que le problème difficile à résoudre en cryptographie en réseau est de trouver un point donné sur le réseau près de l'origine. En fait, trouver un point particulier est relativement simple. Le problème difficile est de trouver un point inconnu qui se trouve près de l'origine. L'article a été modifié pour refléter ce fait.