International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.

Details

Luca De Feo (#269)
Name Luca De Feo
Personal Homepage http://www.lix.polytechnique.fr/~defeo
Institution Ecole Polytechnique
Topic of his/her doctorate. Fast Algorithms for Towers of Finite Fields and Isogenies
Category foundations
Keywords elliptic curves, isogenies, finite fields
Ph.D. Supervisor(s) François Morain, Éric Schost
Year of completion 2010
Abstract

In this thesis we apply techniques from computer algebra and language theory to speed up the elementary operations in some specific towers of finite fields. We apply our construction to the problem of computing isogenies between elliptic curves and obtain faster (both asymptotically and in practice) variants of Couveignes’ algorithm.

The document is divided in four parts. In Part I we recall some basic notions from algebra and complexity theory. Part II deals with the transposition principle: in it we generalize ideas of Bostan, Schost and Lecerf, and show that it is possible to automatically transpose computer programs without losses in time complexity and with a small loss in space complexity. Part III combines the results on the transposition principle with classical techniques from elimination theory; we apply these ideas to obtain asymptotically optimal algorithms for the arithmetic of Artin-Schreier towers of finite fields. We also describe an implementations of these algorithms. Finally, in Part IV we use the previous results to speed up Couveignes’ algorithm and compare the result with the other state of the art algorithms for isogeny computation. We also present a new generalization of Couveignes’ algorithm that computes isogenies of unknown degree.

Last Change 2011-02-24 12:02:43
To provide an update on this entry, please click .

Contact: phds (at) iacr.org

[ IACR home page ] [ IACR PhDs page ] © IACR