Fonctionne avec Indico
v3.2.9
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 cette optique, il est important de pouvoir faire des calculs en pratique pour ne pas se contenter d'arguments asymptotiques, notamment sur dans des corps de grande dimension. Les algorithmes connus pour résoudre Ideal-SVP nécessitent de calculer des groupes de S-unités du corps de nombres considéré. Une étape courante pour calculer ces objets est une étape de saturation, qui permet d'agrandir un sous-groupe de rang plein en y adjoignant des racines p-èmes d'éléments, pour p un nombre premier. Cette étape nécessite donc le calcul des racines de ces éléments, qui est un cas particulier du calcul de racines polynomiales. Par conséquent, améliorer les performances des algorithmes permettant de retrouver les racines de polynômes à coefficients dans un corps de nombres peut avoir un impact important sur notre capacité à étudier Ideal-SVP en pratique.
Dans cet exposé je présenterai d'abord l'étude d'extensions de Kummer réelles effectuée pendant ma thèse. J'ai étudié la possibilité de retrouver des générateurs courts d'idéaux principaux sur ces corps, et j'exhibe une sous-famille pour laquelle le problème semble plus difficile à résoudre en pratique (collaboration avec Thomas Plantard et Willy Susilo).
Je décrirai ensuite le travail fait pendant mon post-doctorat sur la possibilité de résoudre ISVP dans des corps cyclotomiques. Nous utilisons des générateurs courts de l'idéal de Stickelber 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 avec Olivier Bernard, Thuong Huy et Adeline Roux-Langlois).
Je finirai (si le temps le permet) par une description de mon travail sur la résolutions d'équations polynomiales dans des corps de nombres par des plongements complexes. Je montre notamment comment se servir d'une structure d'extension L/K pour se ramener à des décodages d'éléments de K au lieu de L et développe des observations heuristiques poour améliorer l'efficacité des calculs en pratique (travail avec Thomas Plantard et Willy Susilo)