Sélection de polynômes pour TNFS (Tower Number Field Sieve) et automorphismes.

Dans cet exposé, on s’intéresse au calcul de logarithme discret dans les corps finis \(GF(p^n)\) avec p un nombre premier et un degré d’extension n petit et composé, par exemple n=12, n=24. Ce cas de figure apparait en cryptographie basée sur les couplages, avec les courbes BLS12 et BLS24, où le groupe d’arrivée du couplage est un sous-groupe multiplicatif de \(GF(p^12)\) ou \(GF(p^24)\).
En cryptanalyse classique pour le calcul de log discret dans les corps finis, les meilleurs algorithmes sont des variantes du crible algébrique, ou number field sieve en anglais. En 2015 puis 2016, les algorithmes TNFS puis exTNFS (extended tower number field sieve) ont été proposés. Ils utilisent une tour d’extensions pour définir deux corps de nombres distincts, qui ont un sous-corps en commun. On cherche s’il existe des polynômes de définition particuliers pour ces corps de nombres qui permettent un gain d’efficacité sur les étapes suivantes de l’algorithme TNFS, notamment par l’existence d’automorphismes. Savoir si de tels polynômes existent et pouvoir les lister exhaustivement permettrait une meilleure estimation du temps de calcul de logarithme discret, et par conséquent un dimensionnement des tailles de paramètres plus optimisé pour un usage cryptographique.

Aurore Guillevic, CR, CAPSULE, Inria Rennes