Cycles of supersingular elliptic curves for pairing-based proof systems

Dans le monde numérique, prouver que l'on connaît un secret sans révéler le secret lui-même est un outil puissant. C'est le cœur de la cryptographie moderne, où les « systèmes de preuve » permettent à un ordinateur de convaincre un utilisateur qu'un calcul a été effectué correctement, sans avoir besoin de réexécuter l'intégralité du calcul. Pour que ces preuves soient utiles dans le monde réel, elles doivent être courtes et rapides à vérifier. Un type spécifique de preuve, connu sous le nom d'argument non interactif succinct, est devenu une pierre angulaire de cette technologie. Pour rendre ces preuves encore plus puissantes, des chercheurs ont développé un moyen de les empiler, permettant à une preuve de vérifier une autre, créant ainsi une chaîne de confiance qui peut croître indéfiniment. Ce processus, appelé récursion, est le moteur de certaines des technologies de confidentialité et de mise à l'échelle les plus avancées utilisées aujourd'hui. Cependant, la construction de ces chaînes nécessite un type de fondement mathématique très spécifique : des paires de courbes elliptiques qui s'emboîtent parfaitement comme des pièces de puzzle. Pendant des années, les seules pièces connues répondant à cette description étaient rares, difficiles à trouver et limitées en nombre, créant un goulot d'étranglement pour la technologie.

Une équipe de chercheurs vient de découvrir une nouvelle façon de générer ces paires de courbes essentielles, débloquant un approvisionnement vaste et auparavant inaccessible. Ils ont découvert qu'en utilisant une classe différente d'objets mathématiques appelés courbes supersingulières, ils peuvent construire une famille infinie de ces paires de pièces de puzzle. Contrairement à la méthode précédente, qui reposait sur un ensemble étroit de conditions rendant la recherche de nouvelles paires dépendante de la chance et d'un effort de calcul immense, cette nouvelle approche fonctionne de manière fiable pour presque n'importe quel nombre choisi. Les chercheurs ont démontré qu'ils pouvaient construire ces nouveaux cycles et les connecter à d'autres courbes efficaces pour former ce qu'ils appellent des « lollipops » (sucettes). Ces structures permettent au travail initial et lourd de la preuve de se dérouler sur un corps mathématique petit et rapide, tandis que l'empilement récursif se fait sur le cycle plus grand et plus sécurisé. Dans une recherche pratique, ils ont construit avec succès dix-huit exemples distincts de ces nouvelles structures, offrant une ressource flexible et abondante pour la prochaine génération de systèmes numériques sécurisés.

Le voyage vers cette découverte a commencé par une limitation de la technologie existante. Le standard actuel de ces systèmes de preuve récursive repose sur un arrangement spécifique de deux courbes elliptiques, souvent appelé cycle. Dans cet arrangement, le nombre de points sur la première courbe correspond à la taille du corps définissant la seconde, et vice versa. Cet équilibre délicat permet à la preuve de passer d'une courbe à l'autre de manière fluide. Pendant plus d'une décennie, la seule façon connue de construire de tels cycles utilisait des courbes « ordinaires », une méthode développée par Miyaji, Nakabayashi et Takano. Bien que cette méthode fonctionne en théorie, elle est extrêmement rare en pratique. Trouver une nouvelle paire nécessite de résoudre des équations mathématiques complexes où les nombres doivent être parfaitement ajustés. À mesure que les exigences de sécurité augmentent, la probabilité de tomber sur une paire valide chute presque à zéro. C'est comme essayer de trouver un grain de sable spécifique sur une plage qui répond à des critères précis ; la plage est infinie, mais les bons grains sont d'une rareté extrême. Cette rareté a forcé les développeurs soit à utiliser des paramètres plus anciens et moins sécurisés, soit à abandonner l'idéal de la récursion non bornée pour des chaînes plus courtes et limitées.

Les chercheurs ont réalisé que le goulot d'étranglement n'était pas le concept même du cycle, mais le type spécifique de courbe utilisé. Ils ont porté leur attention sur les courbes « supersingulières ». Il s'agit d'une variété mathématique différente qui, bien que moins courante dans la cryptographie standard, possède des propriétés uniques qui les rendent idéales pour cette tâche spécifique. Le compromis est que ces courbes doivent être définies sur des corps mathématiques légèrement plus grands, ce qui rend certains calculs un peu plus lourds. Cependant, le bénéfice est écrasant : la nouvelle construction fonctionne pour presque n'importe quel nombre choisi, à condition qu'il réponde à un test de primalité de base. Il n'est pas nécessaire de traquer des nombres rares ou chanceux. Les chercheurs ont montré que pour tout nombre valide, ils pouvaient générer immédiatement une paire de courbes supersingulières fonctionnelle. Cela transforme le problème d'une chasse au trésor en un processus de fabrication. Au lieu de trouver quelques exemples dispersés, ils peuvent désormais produire un nombre infini de ces cycles à la demande.

Pour prouver que ce concept fonctionne dans le monde réel, l'équipe ne s'est pas contentée de la théorie ; elle a construit un moteur de recherche pour trouver des exemples concrets. Ils ont entrepris de construire ce qu'ils appellent des « lollipops ». Imaginez une sucette dont le bâton est une chaîne de courbes efficaces et la partie ronde en haut est le cycle récursif. Le bâton permet à la preuve de commencer sur un corps petit et rapide, rendant les étapes initiales du calcul très rapides. La partie ronde, le cycle, permet à la preuve d'être empilée et vérifiée de manière récursive sans limite. Les chercheurs ont développé un algorithme pour trouver ces structures en résolvant un type spécifique de puzzle numérique connu sous le nom d'équation de Pell. Ils ont exécuté cet algorithme sur des ordinateurs puissants, cherchant à travers des millions de possibilités. La recherche a été un succès. Ils ont trouvé dix-huit exemples distincts de ces lollipops, variant en taille pour supporter des niveaux de sécurité allant de 80 bits jusqu'à 128 bits et au-delà. L'un de leurs exemples, une instance large avec un corps de 956 bits, a même repoussé les limites de l'intérêt pratique, montrant que ces structures peuvent évoluer pour répondre aux besoins de sécurité futurs.

La signification de ces découvertes réside dans la flexibilité qu'elles offrent aux concepteurs de systèmes. Avec l'ancienne méthode, les concepteurs étaient contraints d'utiliser un ensemble de paramètres spécifiques, souvent inefficaces, car aucune autre option n'existait. S'ils voulaient une sécurité plus élevée, ils devaient accepter des performances plus lentes ou des limites de récursion plus courtes. Avec les nouveaux cycles supersinguliers, les concepteurs peuvent choisir des paramètres optimisés pour la vitesse, tels que des corps où les calculs sont particulièrement rapides, ou des corps possédant des propriétés spécifiques utiles pour l'accélération matérielle. Ils peuvent également choisir de connecter ces cycles à d'autres types de courbes qui ne sont pas « pairing-friendly » (compatibles avec les couplages) mais qui sont extrêmement efficaces pour les étapes initiales d'une preuve. Cette capacité de mélanger et d'associer des composants, créant une « lollipop » personnalisée pour une application spécifique, était impossible avec la technologie précédente. Les chercheurs ont noté que bien que les nouvelles courbes soient légèrement plus grandes dans certaines parties, la capacité d'optimiser le reste du système et l'abondance même des cycles disponibles rendent le compromis avantageux.

L'article conclut en soulignant qu'il s'agit d'une percée constructive. Les chercheurs ont non seulement prouvé que ces cycles existent, mais ils ont également fourni les outils pour les construire et un catalogue de dix-huit exemples fonctionnels. Ils reconnaissent que la prochaine étape consiste à implémenter ces nouveaux cycles dans des logiciels réels afin de mesurer les gains de performance exacts, car les avantages théoriques doivent être mis en balance avec les coûts pratiques des corps plus larges. Cependant, la porte est désormais ouverte. La rareté qui limitait autrefois la croissance des systèmes de preuve récursive a été supprimée. En passant des courbes ordinaires aux courbes supersingulières, les chercheurs ont fourni un nouvel approvisionnement infini de blocs de construction mathématiques nécessaires pour sécuriser l'avenir numérique, permettant des systèmes de preuve qui sont non seulement plus sûrs, mais aussi plus adaptables aux divers besoins du monde réel.