| Gwénaël Renault |  |
 |
Date de l'exposé : 27 avril 2012
Sur le calcul d'indice pour résoudre l'ECDLP défini sur un corps finide caractéristique 2.
Dans cet exposé, je présenterai des résultats récents sur le calcul d'indice dans le groupe des points d'une courbe elliptique définie sur un corps fini de caractéristique 2. Le résultat principal est la mise en évidence de structures spécifiques des systèmes polynomiaux intervenant dans ce calcul. Plus précisément, les systèmes polynomiaux sont ceux intervenant dans la résolution du problème de décomposition de points de la variante du calcul d'indice proposée par Diem en 2005. Ces structures permettent, en particulier, la mise en place d'une méthode ad-hoc de résolution des systèmes polynomiaux basée sur la linéarisation. L'algorithme obtenu, reposant sur une heuristique liée à l'algèbre linéaire sous-jacente, est de meilleure complexité que la variante (non heuristique) proposée par Diem sans pour autant mettre à mal la sécurité de l'ECDLP dans le cas binaire. Toutefois, l'utilisation de la linéarisation peut être vue comme une première étape dans l'étude de la résolution de tels systèmes structurés ; des expériences préliminaires font espérer que de meilleurs résultats pratiques et théoriques pourraient être obtenus en utilisant les bases de Gröbner.Résultats basés en partie sur un article d'Eurocrypt 2012 en collaboration avec J.-C. Faugère, L. Perret et C. Petit.
