Le célèbre algorithme de cryptographie obtient une mise à niveau | Magazine Quanta

Dans nos vies de plus en plus numériques, la sécurité dépend de la cryptographie. Envoyez un message privé ou payez une facture en ligne, et vous comptez sur des algorithmes conçus pour garder vos données secrètes. Naturellement, certaines personnes veulent découvrir ces secrets. C'est pourquoi les chercheurs s'efforcent de tester la solidité de ces systèmes pour s'assurer qu'ils ne s'effondreront pas aux mains d'un attaquant intelligent.

Un outil important dans ce travail est l’algorithme LLL, du nom des chercheurs qui publié en 1982 — Arjen Lenstra, Hendrik Lenstra Jr. et László Lovász. LLL, ainsi que ses nombreux descendants, peuvent dans certains cas briser les schémas cryptographiques ; étudier leur comportement aide les chercheurs à concevoir des systèmes moins vulnérables aux attaques. Et les talents de l'algorithme s'étendent au-delà de la cryptographie : c'est également un outil utile dans les domaines mathématiques avancés tels que la théorie informatique des nombres.

Au fil des années, les chercheurs ont perfectionné des variantes du LLL pour rendre l’approche plus pratique – mais seulement jusqu’à un certain point. Aujourd’hui, deux cryptographes ont construit un nouvel algorithme de style LLL avec une efficacité considérablement améliorée. La nouvelle technique, qui a remporté le Prix ​​du meilleur article au Conférence internationale de cryptologie 2023, élargit la gamme de scénarios dans lesquels les informaticiens et les mathématiciens peuvent utiliser des approches de type LLL.

«C'était vraiment excitant», a déclaré Chris Peikert, un cryptographe de l'Université du Michigan qui n'a pas participé à l'article. Cet outil fait l’objet d’études depuis des décennies, a-t-il déclaré. "C'est toujours agréable quand un objectif sur lequel on travaille depuis si longtemps... montre qu'il y a encore des surprises à trouver."

Les algorithmes de type LLL opèrent dans le monde des réseaux : des collections infinies de points régulièrement espacés. Pour visualiser cela, imaginez que vous carrelez un sol. Vous pourriez le recouvrir de tuiles carrées et les coins de ces tuiles formeraient un seul treillis. Vous pouvez également choisir une forme de tuile différente, par exemple un long parallélogramme, pour créer un réseau différent.

Un réseau peut être décrit à l’aide de sa « base ». Il s'agit d'un ensemble de vecteurs (essentiellement des listes de nombres) que vous pouvez combiner de différentes manières pour obtenir chaque point du réseau. Imaginons un réseau dont la base est constituée de deux vecteurs : [3, 2] et [1, 4]. Le réseau correspond à tous les points que vous pouvez atteindre en ajoutant et en soustrayant des copies de ces vecteurs.

Cette paire de vecteurs n’est pas la seule base du réseau. Tout réseau ayant au moins deux dimensions a une infinité de bases possibles. Mais toutes les bases ne sont pas égales. Une base dont les vecteurs sont plus courts et plus proches des angles droits les uns par rapport aux autres est généralement plus facile à utiliser et plus utile pour résoudre certains problèmes informatiques, c'est pourquoi les chercheurs qualifient ces bases de « bonnes ». Un exemple de ceci est la paire de vecteurs bleus dans la figure ci-dessous. Les bases constituées de vecteurs plus longs et moins orthogonaux – comme les vecteurs rouges – peuvent être considérées comme « mauvaises ».

C'est le travail de LLL : donnez-lui (ou à ses frères) la base d'un réseau multidimensionnel, et il en crachera un meilleur. Ce processus est connu sous le nom de réduction de la base du réseau.

Qu’est-ce que tout cela a à voir avec la cryptographie ? Il s’avère que la tâche consistant à casser un système cryptographique peut, dans certains cas, être transformée en un autre problème : trouver un vecteur relativement court dans un réseau. Et parfois, ce vecteur peut être extrait de la base réduite générée par un algorithme de style LLL. Cette stratégie a aidé les chercheurs à renverser des systèmes qui, à première vue, semblent avoir peu à voir avec les réseaux.

D'un point de vue théorique, l'algorithme LLL original s'exécute rapidement : le temps nécessaire à son exécution n'évolue pas de manière exponentielle avec la taille de l'entrée, c'est-à-dire la dimension du réseau et la taille (en bits) des nombres dans le vecteurs de base. Mais il augmente en tant que fonction polynomiale, et « si vous voulez réellement le faire, le temps polynomial n'est pas toujours aussi réalisable », a déclaré Léo Ducas, cryptographe à l'institut national de recherche CWI aux Pays-Bas.

En pratique, cela signifie que l’algorithme LLL original ne peut pas gérer des entrées trop volumineuses. "Les mathématiciens et les cryptographes voulaient pouvoir faire plus", a déclaré Kegan Ryan, doctorant à l'Université de Californie à San Diego. Les chercheurs ont travaillé pour optimiser les algorithmes de type LLL afin de prendre en charge des entrées plus importantes, obtenant souvent de bonnes performances. Pourtant, certaines tâches restent obstinément hors de portée.

Le nouveau document, rédigé par Ryan et son conseiller, Nadia Héninger, combine plusieurs stratégies pour améliorer l'efficacité de son algorithme de style LLL. D’une part, la technique utilise une structure récursive qui divise la tâche en morceaux plus petits. D’autre part, l’algorithme gère soigneusement la précision des chiffres impliqués, trouvant un équilibre entre rapidité et résultat correct. Les nouveaux travaux permettent aux chercheurs de réduire les bases de réseaux de milliers de dimensions.

Les travaux antérieurs ont suivi une approche similaire : A papier 2021 combine également la récursivité et la gestion de précision pour accélérer le travail sur de grands réseaux, mais cela ne fonctionnait que pour des types spécifiques de réseaux, et pas pour tous ceux qui sont importants en cryptographie. Le nouvel algorithme se comporte bien sur une plage beaucoup plus large. "Je suis vraiment heureux que quelqu'un l'ait fait", a déclaré Thomas Espitau, chercheur en cryptographie au sein de la société PQShield et auteur de la version 2021. Le travail de son équipe a offert une « preuve de concept », a-t-il déclaré ; le nouveau résultat montre que « vous pouvez effectuer une réduction de réseau très rapide et de manière saine ».

La nouvelle technique a déjà commencé à s’avérer utile. Aurel Page, un mathématicien de l'institut national de recherche français Inria, a déclaré que lui et son équipe avaient mis en œuvre une adaptation de l'algorithme pour travailler sur certaines tâches informatiques de théorie des nombres.

Les algorithmes de type LLL peuvent également jouer un rôle dans la recherche liée aux systèmes de cryptographie sur réseau conçus pour rester en sécurité même dans un avenir doté de puissants ordinateurs quantiques. Ils ne constituent pas une menace pour de tels systèmes, car pour les supprimer, il faut trouver des vecteurs plus courts que ceux que ces algorithmes peuvent atteindre. Mais les meilleures attaques connues par les chercheurs utilisent un algorithme de type LLL comme « élément de base », a déclaré Wessel van Woerden, cryptographe à l'Université de Bordeaux. Dans les expériences pratiques visant à étudier ces attaques, cet élément de base peut tout ralentir. Grâce à ce nouvel outil, les chercheurs pourraient être en mesure d'élargir la gamme d'expériences qu'ils peuvent exécuter sur les algorithmes d'attaque, offrant ainsi une image plus claire de leurs performances.

Quanta mène une série d’enquêtes pour mieux servir notre public. Prenez notre enquête auprès des lecteurs en informatique et vous serez inscrit pour gagner gratuitement Quanta marchandise.