Tutorial on Elliptic and Hyperelliptic Curve Cryptography 2007

This Tutorial on Elliptic and Hyperelliptic Curve Cryptography is held September 3-4, 2007, directly before ECC 2007 at the University College Dublin. The lecture rooms are in the building "Health Sciences Centre". On Monday we are in A005 and Tuesday in the adjacent room A006.

Topics

This course is intended for graduate students and interested researchers in the field of cryptography and mathematics. The participants are expected to be familiar with finite fields and have some background in implementations, some experience with elliptic curves is helpful but not necessary.

This tutorial will be similar in nature to the summer schools held before ECC the last 3 years (for links see the end of this section). However, the tutorial is only 2 days instead of the full 5 days we offered during the past years. The objective of the tutorial is to prepare for the following ECC conference. As an example let me mention the talks on efficient arithmetic on ECC and HECC by Gaudry and Bernstein/Lange. The tutorial will provide explanations on the computation in Weierstrass form and explain projective and other inversion-free coordinate systems. This means that the new results will not be presented in the tutorial but enough background information is given to appreciate the new results.

The course starts with an introduction to elliptic and hyperelliptic curves and details arithmetic in their ideal class group. We give the Hasse-Weil bounds for the group order and explain specifics for curves over finite fields. We also consider possible special choices like Koblitz curves which are defined over subfields and GLV curves which allow to speed up the computation of scalar multiples (the main operation in curve based cryptography) by using efficiently computable endomorphisms.

A comparably new topic in curve based cryptography are pairings. They have been studied in mathematics since many years but only the constructive application of pairings in cryptographic protocols raised interest in the efficient computation of the Weil and Tate-Lichtenbaum pairing. We introduce the pairings and explain optimizations for their implementation.

We present generic methods of computing discrete logarithms and detail special methods applicable to curves like index calculus attacks on hyperelliptic curves of large genus and attacks via Weil descent.

Links to previous summer schools:

Exercises

• Monday
• Tuesday

Speakers

Slides

Schedule

Each day has 4 lectures of 1h each, interleaved with breaks and a lunch break. Lectures start at 09:30 the morning. In the afternoon from 15:30-17:00 we plan to have an exercise session with a presentation of the solutions from 17:00 - 17:30.

Please note that on Tuesday, September 4th, Joe Silverman will give a public lecture at 19:30. More information can be found at the ECC homepage.

 9:00-      Registration
 9:30-10:30 Background elliptic curves over R and Fq     Daniel J. Bernstein 
10:30-11:00 coffee break
11:00-12:00 Background elliptic curves over Q and Fq     Tanja Lange
12:00-13:00 Generic attacks & basics of index calculus   Daniel J. Bernstein 
13:00-14:30 lunch
14:30-15:30 The Picard group                             Isabelle Déchène
15:30-17:00 exercises
17:00-17:30 answers

 9:30-10:30 EC over Q II and pairing background          Tanja Lange 
10:30-11:00 coffee break
11:00-12:00 Fast arithmetic on ECC and HECC              Peter Birkner
12:00-13:00 Pairing implementation                       Mike Scott
13:00-14:30 lunch
14:30-15:30 Weil descent incl. Index calculus on HECC    Tanja Lange
15:30-17:00 exercises
17:00-17:30 answers

Literature

• R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen, and F. Vercauteren, "Handbook of Elliptic and Hyperelliptic Curve Cryptography", CRC Press.
  This book finally has a homepage. We display a different chapter every month.
• I. F. Blake, G. Seroussi and N. P. Smart, "Elliptic curves in cryptography", Cambridge University Press.
• I. F. Blake, G. Seroussi and N. P. Smart, "Advances in Elliptic Curve Cryptography", Cambridge University Press.
• D. Lorenzini, "An Invitation to Arithmetic Geometry", Graduate studies in mathematics 9, AMS, 1996
• D. Hankerson, A. J. Menezes and S. A. Vanstone, "Guide to elliptic curve cryptography", Springer Verlag.
• J. Silverman, "The Arithmetic of Elliptic Curves", Springer Verlag.
• J. Silverman, "Advanced topics in the arithmetic of elliptic curves", Springer Verlag.
• J. Silverman and J. Tate, "Rational points on elliptic curves", Springer Verlag.

Registration

Registration is free of charge to students. For non-students to attend the tutorial, payment is required. All registrants must complete the registration form provided on the ECC main page.