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.
Prerequisites: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.
Content: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.
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 & answersTuesday
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 & answersWednesday
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 & answersThursday
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 & answersFriday
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