POKEx: Performance analysis of POKE-key exchange and SIDH-variants

Imaginez que l'internet est une ville géante et trépidante où tout le monde s'envoie des lettres secrètes. Pour garder ces lettres en sécurité, nous utilisons des « verrous » appelés chiffrement. Pendant des décennies, les meilleurs verrous ont été fabriqués à l'aide de problèmes mathématiques faciles à résoudre dans un sens, mais incroyablement difficiles à inverser, comme mélanger des couleurs de peinture. Cependant, les scientifiques craignent qu'à l'avenir, des ordinateurs surpuissants (appelés ordinateurs quantiques) puissent défaire ces verrous instantanément, laissant nos secrets totalement exposés. Pour contrer cela, des chercheurs construisent de nouveaux verrous basés sur une branche de l'mathématique étrange et magnifique appelée « isogénie ». Pensez aux isogénies comme à un type spécial de pont qui relie différentes formes (courbes mathématiques). Le secret du verrou est le chemin spécifique que l'on emprunte pour traverser le pont. Pendant longtemps, le design de pont le plus populaire s'appelait SIDH. Il était célèbre parce que ses verrous étaient minuscules et rapides, ce qui en faisait un candidat de premier plan pour protéger notre futur monde numérique.

Cependant, en 2023, une paire de chercheurs a découvert une astuce ingénieuse pour briser le pont SIDH. Ils ont découvert que les concepteurs du pont avaient accidentellement laissé une carte du chemin visible pour quiconque la regardait, permettant ainsi de découvrir l'itinéraire secret en quelques secondes. Ce fut un coup dur, car cela signifiait que le verrou le plus prometteur pour résister au quantique était en réalité cassé. Depuis lors, les scientifiques tentent frénétiquement de construire de nouveaux ponts qui cachent mieux la carte. Certains ont essayé de couvrir la carte avec une couverture (masquage), tandis que d'autres ont essayé de construire le pont avec des matériaux différents. La grande question restait : pouvons-nous construire un pont qui soit à la fois incassable et assez rapide pour être utilisé dans le monde réel ?

Ce document, intitulé « POKEx », intervient sur ce chantier de construction chaotique pour tester un nouveau design de pont brillant appelé POKÉ. Les auteurs, Hyeonhak Kim et Suhri Kim, ont décidé de transformer la méthode de chiffrement POKÉ en un système complet d'échange de clés (qu'ils appellent POKEx) et de la faire concourir contre les autres principaux concurrents essayant de réparer le pont SIDH brisé. Ils ne se sont pas contentés de deviner ; ils ont construit des versions fonctionnelles de ces systèmes et les ont chronométrées sur un ordinateur puissant. Leur principale conclusion est que POKEx est actuellement le plus rapide et le plus efficace de tous les ponts basés sur les isogénies. Dans leurs tests, il était environ 21 fois plus rapide que la meilleure alternative suivante (terSIDH) et près de 65 fois plus rapide qu'un autre design populaire (CSIDH). Bien qu'il soit toujours plus lent que certains autres types de verres résistants au quantique, sa vitesse et sa petite taille en font un candidat très prometteur pour l'avenir, offrant un moyen de garder nos secrets numériques en sécurité sans ralentir l'internet.

L'histoire du pont brisé et de la nouvelle solution

Pour comprendre pourquoi ce document est important, nous devons d'abord regarder le problème du « pont ». Dans le monde de la cryptographie, un « échange de clés » est comme deux personnes convenant d'un mot de passe secret sans jamais le dire à voix haute. Pendant longtemps, le système SIDH a été l'acteur vedette. Il utilisait des courbes elliptiques supersingulières — imaginez que ce sont des formes complexes et sinueuses dans un univers mathématique. La magie de SIDH était qu'il utilisait des « points de torsion », qui sont comme des points de repère spécifiques sur ces courbes, pour construire le pont. Le système était si efficace qu'il utilisait de petites clés (l'équivalent numérique d'un verrou minuscule et léger) et était très rapide.

Cependant, le pont SIDH présentait une faille fatale. Pour construire le pont, le système devait publier certaines informations sur les points de repère (points de torsion) qu'il utilisait. En 2023, Castryck et Decru ont trouvé un moyen d'utiliser ces points de repère publiés, combinés à une astuce mathématique ingénieuse appelée « colle et division de Kani » (Kani's glue-and-split), pour reconstruire le chemin secret. C'était comme laisser une trace de miettes de pain qui menait directement au trésor. Une fois cette attaque découverte, SIDH a été considéré comme brisé et retiré de la liste des candidats pour la sécurité future de l'internet.

La course pour réparer le pont

Après la chute de SIDH, la communauté de la cryptographie n'a pas abandonné. Elle a commencé à construire de nouveaux ponts pour le remplacer. Certains ont tenté de cacher les points de repère en les recouvrant de bruit aléatoire (une méthode appelée M-SIDH). D'autres ont tenté de changer entièrement la forme du pont en utilisant une « orientation artificielle » (terSIDH). Il y avait aussi CSIDH, un type différent de pont qui n'était pas affecté par la même attaque, mais qui avait ses propres problèmes de vitesse.

Le problème était que ces nouveaux ponts étaient soit trop lents, soit trop volumineux. Couvrir les points de repère avec du bruit nécessitait des nombres beaucoup plus grands pour rester sécurisé, ce qui rendait les verrous lourds et lents à utiliser. Changer la forme du pont (terSIDH) a aidé, mais il y avait toujours des variations de vitesse qui pouvaient être dangereuses. La communauté avait besoin d'une solution qui soit à la fois sécurisée et rapide.

Entrée en scène POKEx : Le démon de la vitesse

C'est ici que le nouveau héros du document, POKEx, entre en scène. POKEx est basé sur un schéma appelé POKÉ, qui a été proposé récemment par Basso et Maino. Les auteurs de ce document ont pris POKÉ et l'ont transformé en un système complet d'échange de clés, complet avec toutes les étapes nécessaires pour générer des clés et échanger des secrets en toute sécurité.

La recette secrète de POKEx réside dans la façon dont il gère les « points de repère ». Au lieu d'utiliser simplement des chemins unidimensionnels comme l'ancien SIDH, POKEx utilise une « représentation bidimensionnelle ». Imaginez essayer de traverser une rivière. SIDH était comme marcher sur une seule planche. Si quelqu'un voyait où vous posiez le pied, il pouvait deviner votre chemin. POKEx, cependant, est comme marcher sur une grille de planches où vous pouvez vous déplacer dans deux directions à la fois. Cela rend le chemin beaucoup plus difficile à deviner. De plus, POKEx utilise un type spécial de corps mathématique (un nombre premier de la forme $2^a3^b5^c-1$) qui permet des calculs très rapides, contrairement aux autres nouveaux ponts qui devaient utiliser des nombres beaucoup plus grands et plus lents.

Le grand affrontement : Que disent les chiffres ?

Les auteurs ne se sont pas contentés de parler de POKEx ; ils l'ont mis à l'épreuve. Ils ont construit des logiciels pour faire fonctionner POKEx aux côtés des autres principaux concurrents : M-SIDH, terSIDH et CSIDH. Ils les ont tous réglés sur le même niveau de sécurité (niveau de sécurité NIST 1, qui est la norme pour protéger les données gouvernementales hautement secrètes) et ont chronométré le temps nécessaire pour échanger une clé.

Les résultats sont frappants.

• M-SIDH était le plus lent du groupe, prenant près de 190 secondes pour faire ce que POKEx faisait en une fraction de seconde. Les auteurs ont noté que cela rend M-SIDH impraticable pour une utilisation réelle.
• terSIDH était beaucoup plus rapide que M-SIDH, mais prenait quand même environ 6,5 secondes.
• CSIDH a pris environ 20 secondes.
• POKEx, cependant, a terminé la tâche en seulement 306,95 millisecondes (environ 0,3 seconde).

Pour mettre cela en perspective, POKEx était 21,21 fois plus rapide que terSIDH et 64,97 fois plus rapide que CSIDH. Cela fait de POKEx le champion actuel de l'échange de clés par isogénie.

Est-ce parfait ?

Le document prend soin de ne pas présenter cela comme une solution « parfaite ». Bien que POKEx soit le plus rapide parmi les ponts d'isogénie, il est toujours beaucoup plus lent que d'autres types de verres résistants au quantique, comme ML-KEM (qui n'a pris que 0,10 milliseconde dans le test). Cependant, les auteurs soulignent un compromis crucial. ML-KEM est rapide, mais ses « verrous » (clés publiques et textes chiffrés) sont énormes, occupant beaucoup d'espace sur l'internet. POKEx, en revanche, possède des clés très petites (seulement 324 octets pour la clé publique), ce qui signifie qu'il utilise moins de bande passante. Dans un monde où la vitesse de l'internet et les limites de données comptent, cette petite taille est un avantage massif.

L'essentiel

Ce document montre que bien que l'ancien pont SIDH soit brisé, la route vers un nouveau pont sûr est ouverte. POKEx est actuellement le candidat le plus prometteur de la famille des isogénies, offrant une combinaison rare de haute vitesse et de petite taille. Il prouve que nous pouvons construire des verres résistants au quantique qui ne ralentissent pas nos vies numériques. Bien qu'il ait encore besoin de plus de travail pour rattraper la vitesse d'autres méthodes résistantes au quantique, son efficacité suggère qu'il pourrait devenir un outil vital pour sécuriser notre futur internet, surtout dans les situations où économiser de l'espace de données est tout aussi important que de gagner du temps.