Summer School on Elliptic and Hyperelliptic Curve Cryptography

Topics

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.

Exercises

• Monday
• Tuesday
• Wednesday
• Thursday
• Friday

Speakers

Schedule

 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

• Efficient arithmetic in finite fields, Daniel J. Bernstein
• Elliptic curves I, Roger Oyono, was given as a blackboard presentation. Background can be found in Chapter 13 of the Handbook of Elliptic and Hyperelliptic Curve Cryptography.
• Scalar Multiplication and Addition Chains, Peter Birkner
• Generic attacks, Roger Oyono, was given as a blackboard presentation. Notes to come soon.
• HEC I and II was given as blackboard presentations. The material covered is as in the slides of Tanja's lectures Hyperelliptic Curves at the Information Security Summer School (ISSS) 2006, Taiwan; and Arithmetic of hyperelliptic curves over finite fields at Summer School in Wyoming, 2006.
  For more material see Mathematical Background of Public Key Cryptography, IEM Preprint 10 (2003).
• Index calculus attack in finite fields, Roger Oyono, was given as a blackboard presentation. Notes to come soon.
• Elliptic curves II, Reinier Bröker.
• Background mathematics for CM, Reinier Bröker, was given as a blackboard presentation and covered mainly quadratic number fields and algebraic integers. Background can be found in many books on algebra.
• Arithmetic on EC, large characteristic, Daniel J. Bernstein
• Arithmetic on EC, small characteristic, Nicolas Thériault, was given as a blackboard presentation. Formulae for EC in binary fields can be found in Chapter 13 of the Handbook of Elliptic and Hyperelliptic Curve Cryptography.
• Complex multiplication I, Reinier Bröker, was given as a blackboard presentation.
• Index calculus attacks on HEC I, Nicolas Thériault
• Complex multiplication II, Reinier Bröker, was given as a blackboard presentation.
• "Arithmetic on HEC" and "Pairings I & II" were given as blackboard presentations. The material covered is as in the slides of Tanja's lectures Efficient arithmetic on hyperelliptic curves over finite fields at the Information Security Summer School (ISSS) 2006, Taiwan; and Efficient arithmetic on hyperelliptic curves over finite fields & Pairings WCAP, Santos, 2006; Pairings in Cryptography, tutorial at ASIACRYPT 2005.
• Index calculus attacks on HEC II, Nicolas Thériault

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. In September 2006 we have "13. Arithmetic of Elliptic Curves" which should be interesting for the participants.
• 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.