Recherche d’éléments courts dans les réseaux idéaux

Dans la recherche actuelle de primitives pouvant résister à l’utilisation d’un ordinateur quantique, une des pistes majeure se base sur les réseaux euclidiens, et, en particulier, sur le problème Learning With Errors (LWE). En effet, il existe une réduction pire cas - moyen cas vers le problème classique de réseaux qu’est le Shortest Vector Problem (SVP). Pour des raisons d’efficacité, les schémas envisagés se basent sur des versions structurées de LWE, comme Ring ou Module-LWE. Il existe par ailleurs des réductions pire cas - moyen cas de ces problèmes vers le SVP restreint respectivement aux réseaux idéaux (Ideal-SVP) et modules (Module-SVP). C’est pourquoi l’analyse de Ideal-SVP a reçu une attention soutenue ces dernières années.

Dans cet exposé, je ferai d’abord des rappels concernant les réseaux euclidiens, la cryptographie basée sur ces objets, ainsi que les principales attaques algébriques sur Ideal-SVP. Je décrirai ensuite le travail fait pendant mon post-doctorat sur la possibilité de résoudre Ideal-SVP dans des corps cyclotomiques. Nous utilisons des générateurs courts de l’idéal de Stickelberger pour calculer en temps raisonnable le réseau des Log-S-unités pour des corps de dimension aussi grande que 200. Nous faisons également des expériences pour évaluer les performances de l’algorithme Twisted-PHS dans ce mode dégradé (travail accepté à ASIACRYPT 2022, avec Olivier Bernard, Thuong Huy et Adeline Roux-Langlois).