Summer School on Elliptic and Hyperelliptic Curve Cryptography

Topics Exercises Speakers Schedule Slides and Notes Literature


This Summer School on Elliptic and Hyperelliptic Curve Cryptography is part of the Thematic Program in Cryptography at the Fields Institute in Toronto.

There are several Graduate Courses offered this year one of which is this summer school.


This course is intended for graduate students 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. Such pre-knowledge can be gained e.g. in the summer school on "Computational Number Theory and Applications to Cryptography", June 19-July 7, 2006, Laramie, Wyoming, which is also linked to the special program at the Fields Institute.


The objective of the course is to prepare for the following ECC conference - but should be interesting as an individual course to get an overview of the area of curve cryptography, too.

The course starts with an introduction to elliptic and hyperelliptic curves and details efficient arithmetic in their ideal class group. 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. Clearly, pairings can also be used to transfer the discrete logarithm problem (DLP) from the Jacobian of a curve to the DLP in a finite extension field of the ground field.

To avoid attacks by brute force, the group order must be large enough. The Hasse-Weil bound gives bounds on the number of points over finite fields and thus allows to know the size of the groups approximately. However, since the DLP could be solved in subgroups and then computed for the big group with the help of the Chinese Remainder Theorem one needs to ensure that the group order is known and contains a large prime factor. For elliptic curves we explain Schoof's algorithm as a method to count points on curves over prime fields and consider p-adic methods like AGM which are more efficient in the case of small characteristic fields.

A different approach is to construct curves using the CM method. Even though nowadays counting points via Schoof's algorithm is feasible for elliptic curves of cryptographic size this method is still of interest, e.g. it is the main way of constructing non-supersingular curves with low embedding degree which can be useful in pairing based protocols if one wants to avoid supersingular curves for some reason or if a larger embedding degree is desired.



Daniel J. Bernstein (University of Illinois at Chicago, USA)
Peter Birkner (Technical University of Denmark)
Reinier Bröker (University of Calgary, Canada)
Tanja Lange (Eindhoven Technical University and Technical University of Denmark)
Michael Naehrig (RWTH Aachen University, Germany)
Roger Oyono (University of Waterloo, Canada)
Nicolas Thériault (Fields Institute Toronto, Canada)


 8:30-      Registration
 9:00-10:00 Efficient arithmetic in finite fields	Daniel J. Bernstein
10:15-11:15 Elliptic curves I				Roger Oyono
11:30-12:30 Addition chains				Peter Birkner
12:30-14:00 lunch
14:00-15:00 Generic attacks				Roger Oyono
15:30-17:30 exercises & answers
 9:00-10:00 Hyperelliptic curves I			Tanja Lange
10:15-11:15 Hyperelliptic curves II                     Tanja Lange
11:30-12:00 Index calculus attack in finite fields      Roger Oyono
12:00-12:30 Elliptic curves II				Reinier Bröker
12:30-14:00 lunch
14:00-15:00 Background mathematics for CM		Reinier Bröker
15:30-17:30 exercises & answers
 9:00-10:00 Arithmetic on EC, large characteristic      Daniel J. Bernstein
10:15-11:15 Arithmetic on EC, small characteristic      Nicolas Thériault
11:30-12:30 Point counting on EC			Reinier Bröker
12:30-14:00 lunch
14:00-15:00 Complex multiplication I			Reinier Bröker
15:30-17:30 exercises & answers
 9:00-10:00 Index calculus attacks on HEC I		Nicolas Thériault
10:15-11:15 Complex multiplication II			Reinier Bröker
11:30-12:30 Arithmetic on HEC				Tanja Lange
12:30-14:00 lunch
14:00-15:00 Pairings I					Tanja Lange
15:30-17:30 exercises & answers
 9:00-10:00 Pairings II					Tanja Lange
10:15-11:15 Construction of pairing friendly curves	Michael Naehrig
11:30-12:30 Index calculus attacks on HEC II		Nicolas Thériault
12:30-14:00 lunch
14:00-15:00 Summary - how to choose curves		Tanja Lange

Slides and Notes