Elliptic Curves in Cryptography
Fall 2011
Textbook
 Required: Elliptic Curves: Number Theory and Cryptography, 2nd edition by L. Washington.
 Online edition of Washington (available from oncampus computers; click here to set up proxies for offcampus access).
 There is a problem with the Chapter 2 PDF in the online edition of Washington: most of the lemmas and theorems don't display correctly. We are working with Stanford Libraries and the publisher to make a correct version available. In the meantime, here is a PDF file with the missing content.
Lecture Notes
Lucas Garron has graciously agreed to share his lecture notes with the class. These notes are intended to serve as a guide to the topics covered and not as an authoritative source. Neither Lucas nor the course staff shall be held responsible for any errors or omissions.
Syllabus
The syllabus below will be updated periodically throughout the course to indicate the topics and readings for each lecture. Click here for an overview of the topics to be covered.
Lecture 1:
9/26/11

Introduction to ECC
What is cryptography?
What is an elliptic curve? Reading: Washington Appendices B and C 
Fundamentals of elliptic curves  
Lecture 2:
9/28/11

Computing on elliptic curves
[SAGE worksheet]
Why do we use elliptic curves in crypto?
Group law and the point at infinity. Elliptic curves in SAGE. Reading: Washington 2.12.4. 
Lecture 3:
10/ 3/11

Isomorphisms of elliptic curves
Singular curves.
Definition and examples of isomorphisms. jinvariant. Reading: Washington 2.7, 2.8, 2.10. 
Lecture 4:
10/ 5/11

Endomorphisms and torsion
Endomorphisms, degree, separability.
Examples: multiplication by n, Frobenius. Torsion points. Reading: Washington 2.9, 3.1, 3.2. 
Elliptic curves over finite fields  
Lecture 5:
10/10/11

Size and structure of E(F_{q})
[SAGE worksheet]
Structure of ntorsion.
Legendre symbols and point counting. Hasse's theorem Reading:
Washington 4.1, 4.2. 
Lecture 6:
10/12/11

Determining the group order and structure
Characteristic polynomial of Frobenius
Subfield curves Supersingular curves Reading: Washington 4.3, 4.6. 
Elliptic curve cryptosystems  
Lecture 7:
10/17/11

Encryption
Definition of secure encryption
Equivalence of semantic security and realorrandom security ElGamal encryption Attacks on ElGamal Reading:
Washington 6.1, 6.2, 6.4. 
Lecture 8:
10/19/11

Encryption and Signatures
Security of ElGamal encryption
Hybrid encryption Definition of secure signatures Schnorr identification and signatures Reading:
Definition of digital signatures (by Dan Boneh and Victor Shoup). 
Lecture 9:
10/24/11

Signatures
Security of Schnorr signatures
ECDSA Reading: Washington 6.5, 6.6. 
Discrete logarithm attacks  
Lecture 10:
10/26/11

General attacks on the DLP
PohligHellman
Baby stepgiant step Pollard rho and lambda Reading: Washington 5.2. 
Lecture 11:
10/31/11

The MenezesOkamotoVanstone attack
Index calculus in finite fields
Weil pairing MOV attack Reading: Washington 3.3, 5.1, 5.3. 
Lecture 12:
11/ 2/11

Weak elliptic curves
[SAGE worksheet]
Embedding degree
Supersingular curves Anomalous curves Reading:
Washington 5.4. 
Pairingbased cryptography  
Lecture 13:
11/ 7/11

Key exchange and identitybased encryption
[pdf]
Joux 3party key exchange
IBE definitions BonehFranklin IBE scheme Reading:
Washington 6.9 
Lecture 14:
11/ 9/11

IBE and Signatures
Security of BonehFranklin variant
BonehLynnShacham signature scheme Reading:
BonehLynnShacham paper. 
Lecture 15:
11/14/11

Homomorphic Encryption
[pdf]
Homomorphic ElGamal
BonehGohNissim encryption Reading: BonehGohNissim paper, sections 13. 
Algorithms for ECC  
Lecture 16:
11/16/11

Computing the Weil and Tate pairings
Divisors and functions
Defining the pairings Properties of the pairings Miller's algorithm Reading: Washington 11.1, 11.3, 11.4. 
Holiday: 11/21/11 
Thanksgiving break 
Holiday: 11/23/11 
Thanksgiving break 
Lecture 17:
11/28/11

The CM Method of curve construction
Elliptic curves over C
Complex multiplication Computing Hilbert class polynomials Reading: Washington 9.2, 9.3, 10.110.4. 
Advanced topics  
Lecture 18:
11/30/11

Fast factoring and discrete log algorithms on a quantum computer
Guest lecture by Mark Zhandry
Reading: Shor's paper 
Lecture 19:
12/ 5/11

Factoring and primality proving using elliptic curves
Guest lecture by Dan Boneh
Reading: Washington 7.1, 7.2. 
Lecture 20:
12/ 7/11

Weil descent: Attacking elliptic curves over extension fields
Guest lecture by Ed Schaefer
Reading: Washington 13.113.4 