C’est le travail de LLL : donnez-lui (ou à ses frères) la base d’un réseau multidimensionnel, et il en créera 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é Keegan 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 nouvel article, rédigé par Ryan et sa conseillère, Nadia Heninger, 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 : un article de 2021 combine également la gestion de la récursivité et de la précision pour permettre un travail rapide sur de grands réseaux, mais il n’a fonctionné 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 chez 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, mathématicien à l’institut national de recherche français Inria, a déclaré que lui et son équipe ont 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 relative aux systèmes de cryptographie sur réseau conçus pour rester sécurisés 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.
Histoire originale réimprimé avec la permission de Revue Quanta, une publication éditorialement indépendante du Fondation Simons dont la mission est d’améliorer la compréhension publique de la science en couvrant les développements et les tendances de la recherche en mathématiques et en sciences physiques et de la vie.
