Programme

The deployment of elliptic curves in cryptography requires that critical operations (such as the point multiplication) can be efficiently and securely implemented on a wide variety of platforms, ranging from desktop computers to embedded devices and smart cards. In these two lectures, we will try to see a few of the various solutions that exist, and to identify common security pitfalls and how they can be avoided, from both the software and hardware perspectives.

Let E be an elliptic curve over a finite field F_q. The first part of the lecture will study the group structure of E(F_q) as an abelian group, as a symplectic space for the Weil pairing, and finally as an End(E)-module where we will present Lenstra's theorem on the complex multiplication structure of elliptic curves. In the second part we will study how these structures change under isogenies and base field extensions.

What happens when we step outside the realm of elliptic curves? The points of an elliptic curve form a group; for more general algebraic curves, the analogous groups are higher-dimensional objects called Jacobians. In these talks, we will

• describe the geometry of curves and their Jacobians, and the algorithms needed to compute with them efficiently;
• show how to construct Kummer surfaces, useful for high-speed scalar multiplication routines;
• explain why genus 1 and 2 seem like good ideas, but genus >= 3 seems like an increasingly bad idea in cryptography; and
• use the geometry of algebraic curves to attack the DLP in special classes of elliptic curves.

We will highlight algorithmic challenges and unsolved problems, and give a hacker's guide to technical concepts like abelian varieties, polarizations, and theta functions.

We will cover the lineage of algorithms which have led to the current state of the art in computing discrete logarithms in finite fields and elliptic curves. The course will present in particular the variants of the Number Field Sieve adapted to these settings, the quasi-polynomial discrete logarithm algorithm for small characteristic finite fields, as well as the discrete logarithm problem on various instances of higher genus curves.

Sheet with GP commands