Fonctions booléennes, courbes algébriques et multiplication complexe

Thèse soutenue par Jean-Pierre Flori du laboratoire de cryptographie de l'ANSSI le vendredi 3 février 2012.

Jury :

-* Gary McGuire (Rapporteur)
-* Igor Shparlinski (Rapporteur)
-* Andreas Enge (Examinateur)
-* Sihem Mesnager (Examinatrice)
-* Benjamin Smith (Examinateur)
-* Nicolas M. Thiéry (Examinateur)
-* Gérard Cohen (Directeur)
-* Hugues Randriam (Directeur)

Résumé :

Le coeur de cette thèse est l’étude d’objets ou de problèmes mathématiques intéressants en cryptologie. Autant que possible, l’auteur a essayé de mettre en avant les aspects calculatoires de tels problèmes. Les thèmes traités ici sont en effet non seulement propices aux approches expérimentales, mais aussi à une transposition quasiment immédiate des concepts mathématiques en implémentations concrètes.

La première partie de cette thèse est dévolue à l’étude d’une conjecture combinatoire dont la validité assure l’existence de familles infinies de fonctions booléennes dotées de propriétés cryptographiques intéressantes. Quoique particulièrement innocente au premier abord, la validité de cette conjecture reste un problème ouvert. Néanmoins, l’auteur espère que les résultats théoriques et expérimentaux présentés ici permettront au lecteur d’acquérir un tant soit peu de familiarité avec la conjecture.

Dans la seconde partie de ce manuscrit, des liens entre fonctions (hyper-)courbes — une classe particulière de fonctions booléennes —, sommes exponentielles et courbes (hyper)elliptiques sont présentés. Les fonctions (hyper-)courbes sont en effet particulièrement difficiles à classifier et à construire. L’étude des liens mentionnés ci-dessus permet de résoudre de façon élégante des problèmes d’ordre tout aussi bien théorique que pratique.

La troisième et dernière partie pousse plus avant l’étude des courbes (hyper)elliptiques d’un point de vue sensiblement différent. De nombreuses constructions cryptographiques reposent en effet sur l’utilisation de classes particulières de telles courbes qui ne peuvent être construites en utilisant des méthodes classiques. Cependant, la méthode CM permet de donner une réponse positive à ce problème. Les polynômes de classes sont des objets fondamentaux de cette méthode.

Habituellement, leur construction n’est envisagée que pour des ordres maximaux. La modeste contribution de l’auteur est d’expliciter comment une telle construction — la méthode analytique complexe — s’étend aux ordres non-maximaux.