Département Informatique et Réseaux

The core of this thesis is the study of some mathematical objects or problems of interest in cryptography. As much as possible,the author tried to emphasize the computational aspects of these problems. The topics covered here are indeed not only favorable to experimental investigations,but also to the quasi direct translation of the
mathematical concepts involved into concrete algorithms and implementations.The first part is devoted to the study of a combinatorial conjecture whose validity entails the existence of infinite classes of Boolean functions with good cryptographic properties. Although the conjecture seems quite innocuous,its validity remains an open question.
Nonetheless,the author sincerely hopes that the theoretical and experimental results presented here will give the reader a good insight into the conjecture.In the second part,some connections between (hyper-)bent functions —a subclass of Boolean functions —,exponential sums and point counting on (hyper)elliptic curves are presented. (Hyper-)bent functions are known to be difficult to classify and to build explicitly. However,exploring the links between these different worlds makes
possible to give beautiful answers to theoretical questions and to design efficient algorithms addressing practical problems.

The third and last part investigates the theory of (hyper)elliptic curves in a different direction. Several constructions in cryptography indeed rely on the use of highly
specific classes of such curves which can not be constructed by classical means. Nevertheless,the so-called “complex multiplication”method solves some of these problems. Class polynomials are fundamental objects for that method,but their construction is usually considered only for maximal orders.
The modest contribution of the author is to clarify how a specific flavor of their construction —the complex analytic method —extends to non-maximal orders.

Titre: “Fonctions booléennes,courbes algébriques et multiplication complexe”

L’objet principal de cette thèse est l’étude d’objets ou de problèmes mathématiques intéressant d’un point de vue cryptographique. 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égantes 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.