# CO 485/685: Public-Key Cryptography (Fall 2015)

Instructor: David Jao
Office hours: MWF 2:30pm-3:20pm

Teaching assistant: Jason LeGrow, jlegrow(@uwaterloo.ca), MC 5488. Office hours: Mon. 10:00-11:00am & Wed. 9:00-10:00am

Note: Lectures for CO 485/685 will be held in MC 6486, not CPH 3602.

### Midterm materials

• The midterm examination is scheduled to take place on Wednesday, October 21, from 5:30-7:20pm in MC 2038.
• Midterms from previous years: 2013 (http:../../wiki/images/6/6e/CO485-2015-midterm13.pdf), 2014 (http:../../wiki/images/e/e2/CO485-2015-midterm14.pdf)
• This year's midterm: 2015 (http:../../wiki/images/f/ff/CO485-2015-midterm15.pdf)
• Bug in question 2(a): $\iff$ should be $\implies$
• Solutions (http:../../wiki/images/9/97/CO485-2015-solutions15.pdf) to the exam.

### Final examination materials

• The final examination is scheduled to take place on Tuesday, December 8, from 12:30-3:00pm in AL 105.
• Final exams from previous years: 2010 (http:../../wiki/images/8/82/CO485-2015-final10.pdf), 2013 (http:../../wiki/images/9/91/CO485-2015-final13.pdf), 2014 (http:../../wiki/images/f/fc/CO485-2015-final14.pdf)

### Assignments

• Assignment 1 (due September 28).
• Problems 1.11, 1.24, 1.27, and 5.46 from the textbook (2nd edition!).
• Solutions (http:../../wiki/images/4/48/Co485-2015-s1.pdf)
• Assignment 2 (due October 14).
• Problems 1.33, 2.25, 3.15, and 3.39 from the textbook, AND:
• Prove that the Goldwasser-Micali cryptosystem (Section 3.10) is IND-CPA.
• You may find the SageMath Cloud (https://cloud.sagemath.com/) helpful for problem 3.15. Here is a copy (https://cloud.sagemath.com/projects/a8f5bfd4-ef5c-4b4a-827d-67b936bdd853/files/2015-10-09-141753.sagews) of what I presented in class. (You will need a free account on SageMath Cloud to open this link.) Watch out for Carmichael numbers!
• Solutions (http:../../wiki/images/3/3a/Co485-2015-s2.pdf)
• Assignment 3 (http:../../wiki/images/1/19/Co485-2015-a3.pdf) (due November 4).
• Solutions (http:../../wiki/images/3/35/Co485-2015-s3.pdf)
• Assignment 4 (due November 18).
• Problems 6.9, 6.10, and 6.16 from the textbook, plus the following additional problem:
• Recall that the full Fujisaki-Okamoto transform has encryption function $m \mapsto (E(\sigma; H_2(m,\sigma)), m \oplus H_1(\sigma))$. Prove that the full Fujisaki-Okamoto transform is IND-CCA2. State any necessary assumptions.
• Solutions (http:../../wiki/images/8/84/Co485-2015-s4.pdf)
• Assignment 5 (due December 2).
• Problems 6.43 and 6.49 from the textbook, plus the following additional problem:
• Show that the hash function defined in footnote 14 of page 359 of the textbook is insecure when used in the Boneh-Franklin identity-based cryptosystem described in Table 6.12 of the textbook. Explain how you would construct a hash function which is secure for this application.
• Solutions (http:../../wiki/images/1/13/Co485-2015-s5.pdf)