Stage de M2 – Protocoles d'échange de clefs à base d'isogénies October 31, 2016

Contexte

Une isogénie est un morphisme surjectif et de noyau fini de variétés abéliennes. Les exemples les plus simples d’isogénies sont les morphismes algébriques de courbes elliptiques qui préservent les points à l’infini.

La cryptographie à base d’isogénies est une des branches les plus jeunes de la cryptographie asymétrique. Initiée il y a seulement 10 ans par les travaux sur les réductions de logarithmes discret1 2 3, et sur les fonctions de hachage prouvablement sûres4, elle s’est ensuite enrichie de protocoles d’échange de clef5 6 7. Il existe essentiellement deux protocoles d’échange de clefs à base d’isogénies : un basé sur les courbes elliptiques ordinaires5, et un autre basé sur les courbes elliptiques supersingulières6. Ces deux protocoles ont tous les deux l’intérêt de résister à des cryptanalyses par ordinateur quantique (algorithme de Shor), mais seulement le deuxième est considéré suffisamment efficace pour être utilisable en pratique.

Toutes les constructions cryptographiques à base d’isogénies reposent sur des problèmes de recherche de chemins dans des graphes d’isogénies ; ce sont des (multi)-graphes non-orientés où les sommets sont des variétés abéliennes à isomorphisme près, et les arêtes sont les isogénies.

La structure des graphes d’isogénies est régie par celle des anneaux d’endomorphismes des variétés abéliennes. Dans le cas des courbes elliptiques ordinaires, la théorie de la multiplication complexe lie les isogénies aux idéaux fractionnaires d’un corps de nombres quadratique imaginaire8 9. Dans le cas des courbes elliptiques supersingulières, ce sont les idéaux à gauche des ordres maximaux d’une algèbre de quaternions qui jouent le même rôle8 10. Ces théories se généralisent aux variétés abéliennes de dimension supérieure11 12 13, mais elles ne sont pas aussi complètes que pour le cas elliptique.

Sujet du stage

Le but du stage est d’étudier le protocole d’échange de clefs de Rostovtsev et Stolbunov5, d’en proposer une variante efficace, et d’en estimer soigneusement les paramètres de sécurité par une étude des attaques quantiques connues.

On cherchera des pistes pour améliorer le protocole dans les techniques utilisées dans les protocoles à base d’isogénies supersingulières, ainsi que dans les généralisations aux dimensions supérieures. L’analyse de sécurité se fera en tenant compte des modèles de sécurité en cryptographie classique, ainsi qu’en cryptographie post-quantique.

En cas de succès, le stage pourra se poursuivre naturellement par une thèse en cryptographie à base de courbes elliptiques et isogénies : construction de nouveaux cryptosystèmes, cryptanalyse, calcul d’anneaux d’endomorphismes, etc.

Compétences recherchées

  • Connaissances mathématiques en algèbre, théorie des nombres et géométrie (corps finis, corps de nombres, courbes elliptiques, …).

  • Connaissances en algorithmique (par ex.: grands entiers, factorisation, primalité, arithmétique des courbes elliptiques).

  • Maîtrise d’un système de calcul formel (par ex., SageMath, Pari/GP, Magma).

  • Connaissance d’un langage de programmation.

Aucune connaissance en calcul quantique n’est requise, mais ceci peut être un plus.

Laboratoire d’accueil

Le stage s’effectuera dans l’équipe GRACE de l’Inria Saclay, sous la direction de Luca De Feo et de François Morain. Le stagiaire sera amené à interagir avec le Laboratoire Cryptographie et Composants de l’ANSSI.

Pour candidater, envoyez un email à luca.de-feo@uvsq.fr en joignant votre CV et une lettre de motivation.

Bibliographie