Vendredi 17 février 2012 à 14h30 en salle B555
Luca De Feo / Jérôme Plût (Laboratoire PRiSM, Université de Versailles)

Titre : Encore un cryptosystème basé sur les isogénies

Résumé :
Il est bien connu que les graphes de courbes elliptiques isogènes ont une structure de graphe de Ramanujan, ce qui garantit des bonnes propriétés de mixage pour les marches aléatoires. Cette observation a été utilisée à plusieurs reprises pour construire des cryptosystèmes basés sur la difficulté supposée de calculer explicitement une isogénie entre deux courbes elliptiques données.
Rostovstev et Sotlbunov on proposé un protocole à la Diffie Hellman où les clefs secrètes sont des chemins d'isogénies de petit degré et la clef partagée est formée en composant la deux chemins secrets. La raison pour laquelle ce protocole marche est que le groupe des classes agit fidèlement et transitivement sur le graphe des courbes elliptiques isogènes. Le protocole de Rostovstev et Stolbunov est peu efficace et présente un intérêt purement théorique ; les auteurs ont suggéré qu'il pourrait être utilisée dans un contexte post-quantique, cependant Childs, Jao et Soukharev ont montré qu'il existe un algorithme quantique qui calcule une isogénie entre courbes elliptiques ordinaires en temps sous-exponentiel.
L'attaque de Childs et al. repose justement sur l'action du groupe de classes, qui est commutatif. Dans ce travail, en commun avec Jao, nous proposons un cryptosystème basé sur la difficulté de calculer une isogénie entre courbes elliptiques supersingulières. Dans le cas supersingulier, l'anneau d'endomorphismes n'est pas commutatif et le groupe des classes n'est plus bien défini, par conséquent l'attaque de Childs et al. ne s'applique plus. En l'absence de l'action du groupe des classes, notre protocole d'échange de clef doit passer de l'information en plus par rapport à celui de Rostovstev et Stolbunov ; ceci permet d'établir une action des groupes de torsion des courbes elliptiques sur le graphe, il n'est cependant pas clair que cette information en plus puisse aider à attaquer le protocole.
Notre protocole, déjà dans une implantation naïve en Magma, est sensiblement plus performant que celui de Rostovstev et Stolbunov. Nous avons étudié en détail le problème de son optimisation : avec un mélange de techinques classiques et nouvelles, nous présentons maintenant une implantation mixte en Sage/Cython/C qui a des performances comparables à celles de nombreux protocoles à base de couplages. En particulier, nous présentons un algorithme efficace pour le calcul d'isogénies de degré composé, ayant une structure combinatoire intéressante et parfois même étonnante.