CO 485/685 - Fall 2008

The Mathematics of Public Key Cryptography

Instructor: David Jao

Office hours: Wed. 3:30-4:30, Thurs. 4-5

Course materials

Syllabus (https:../../wiki/images/f/fe/Outline.pdf)
Course notes (https:../../wiki/images/e/e6/Co685.pdf) (updated November 26)
Rabin decryption oracle (https:../../cgi-bin/rabin.cgi)
Quiz 1 (https:../../wiki/images/e/ea/Quiz1.pdf)
AES animation (http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf) (via Wikipedia (https://en.wikipedia.org/wiki/Advanced_Encryption_Standard))

Assignment schedule

This schedule is tentatively made available for planning purposes and may be subject to change.

Assignment 1 (https:../../wiki/images/6/65/Assignment1.pdf) (due September 22)
- Corrected version as of Monday, September 15: In problem 3(a), q-1 should have been p-1, p should have been a prime, and the due date has been moved to Monday.
Assignment 2 (https:../../wiki/images/a/a8/Assignment2.pdf) (due October 3)
- The number in problem 1 is 624142660586694101446291308147581805825611279851037995772020202145871 for those of you who wish to cut and paste it.
Assignment 3 (https:../../wiki/images/4/44/Assignment3.pdf) (due October 17)
- In problem 1, the prime p is $1075 + 129$ . The public key is 421853791186609042825716562661266229106681564402837873445139139395759685625 and the ciphertext is (357087535603338629029169017815297250719503384049242732666037767131122789608, 4551181581441151217382245023086425998289291635511324855776759119834162513230).
Midterm (October 22)
- The midterm will be held in RCH 212 from 4:30 to 6:20.
- The midterm is closed book and closed notes. A non-programmable calculator is allowed.
- The exam covers all material up to and including hash functions (October 8).
- Some practice problems (https:../../wiki/images/7/79/Practice-exam.pdf) are available.
Assignment 4 (https:../../wiki/images/7/70/Assignment4.pdf) (due November 14)
Assignment 5 (https:../../wiki/images/6/62/Assignment5.pdf) (due November 28)
Final exam (December 5)
- The final exam will be held in RCH 212 from 12:30 to 3:00.
- The exam is closed book and closed notes. A non-programmable calculator is allowed.
- Practice problems (https:../../wiki/images/a/a3/Practice-final.pdf) for the final exam.
Project (https:../../wiki/images/0/00/Project.pdf) (CO 685 only; due December 19)

Lectures

September 8: Symmetric vs. public key cryptography. Diffie-Hellman, ElGamal.
Septemebr 10: Examples of public key cryptosystems: RSA, Rabin, GM.
September 12: Polynomial time algorithms, Computational number theory, Euclidean algorithm.
September 15: Modular arithmetic, generators, quadratic residues.
September 17: Euler's criterion, quadratic reciprocity.
September 19: Jacobi symbols, modular square roots.
September 22: Security definitions: one-way, IND-CPA, IND-CCA2
September 24: Primality testing, Solovay-Strassen test
September 26: Integer factorization. Pollard rho algorithm, Dixon's random squares method.
September 29: Running time of integer factorization. Security proofs.
October 1: Discrete logarithms, CDH, DDH, IND-CPA security.
October 3: Pollard rho algorithm for discrete logarithms.
October 6: Pohlig-Hellman algorithm, index calculus.
October 8: Hash functions, preimage resistance, collision resistance.
October 10: Why chosen ciphertext security matters.
October 15: Cryptographic random number generators. Blum-Blum-Shub.
October 17: Hard core predicates. Zero knowledge proofs.
October 20: Proof of correctness and zero knowledge for zero knowledge proofs.
October 22: One round and non-interactive zero knowledge proofs.
October 24: Chosen ciphertext secure cryptosystems. DDN, Fujisaki-Okamoto.
October 27: Proof of security for Fujisaki-Okamoto.
October 29: Digital signature schemes. Security definitions.
October 31: RSA signatures. ElGamal, DSA, Schnorr signature schemes.
November 3: Elliptic curves: motivation, definition, group law
November 5: Size and structure of elliptic curve group and n-torsion points.
November 7: Hasse-Weil bound. Schoof's algorithm. Point compression.
November 10: ECDSA. Bilinear pairings. BLS signatures.
November 12: Full domain hash RSA, proof of unforgeability.
November 14: BDH, tripartite key exchange, non-interactive key exchange, IBE.
November 17: Relationship between pairings, DLOG, and DDH. Embedding degree.
November 19: Divisors and principal divisors.
November 21: Definition of Weil pairing. Proof of bilinearity.
November 24: Efficient computation of the Weil pairing.
November 26: Boneh-Boyen signatures and Boneh-Boyen IBE.
November 28: Security proof for Boneh-Boyen signatures.
December 1: Optimal embedding degrees for type 1 and type 2 pairings.

Retrieved from "http://djao.math.uwaterloo.ca/w/CO_485/685_-_Fall_2008"