Jeudi 8 décembre 2016 à 10h30 en salle F503
Alexandre Wallet (LIP6)
Titre : Le problème de décompositions de points dans les variétés Jacobiennes
Résumé :
L'exposé se concentrera sur les attaques algébriques de type calcul d'indice pour le problème du logarithme discret sur courbes algébriques de genre supérieur à 1. Ces algorithmes se déroulent en deux phases: on ne s'intéressera qu'à la première, appelée phase de récolte, et qui peut être modélisée de plusieurs manières. Le problème sous-jacent est de savoir décomposer efficacement des points de la variété Jacobienne de la courbe en somme d'autres points. On présentera d'abord une approche par crible pour cette phase lorsque des "points lisses" sont recherchés. Cette approche s'adapte à tous les types de courbes de genre plus grand que 1, et est expérimentalement plus efficace que celles de l'état de l'art.
On se concentrera ensuite sur les courbes définies sur des extensions de corps. Dans cette situation, on peut utiliser une variante du calcul d'indice appelée attaque par décomposition. La récolte est alors effectuée par résolution de nombreux systèmes polynomiaux multivariés. On proposera une nouvelle modélisation de ces systèmes, en généralisant la notion de polynômes de sommation elliptique à tout les types de courbes algébriques. Pour cela on fait appel à la théorie de l'élimination, tandis que l'aspect pratique est gérée par des méthodes de bases de Gröbner. Enfin, en caractéristique paire, on présentera des améliorations du processus de résolution des systèmes issus des attaques par décomposition, ainsi que leurs impacts sur la complexité de la résolution par calcul de bases de Gröbner. A l'aide d'une implémentation dédiée, ces améliorations nous permettent d'envisager une attaque par décomposition sur une courbe binaire de genre 2 satisfaisant une borne de sécurité réalistes.