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.

Course materials

• Course outline (https:../../wiki/images/8/8b/CO485-2015-outline.pdf)
• Course text: An Introduction to Mathematical Cryptography (https://www.springer.com/us/book/9781493917105) (2nd ed.) by Hoffstein, Pipher, and Silverman.
  • Online copy of the textbook (https://link.springer.com/book/10.1007%2F978-1-4939-1711-2) (for on-campus computers)
  • Online copy of the textbook (https://login.proxy.lib.uwaterloo.ca/login?url=https://link.springer.com/book/10.1007%2F978-1-4939-1711-2) (for off-campus computers)
• Information on the course project (https:../../wiki/images/e/ec/CO485-2015-project.pdf) (for graduate students)
• Fujisaki-Okamoto transform (https:../../wiki/images/9/98/CO485-2015-FO.pdf)

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 (https:../../wiki/images/6/6e/CO485-2015-midterm13.pdf), 2014 (https:../../wiki/images/e/e2/CO485-2015-midterm14.pdf)
• This year's midterm: 2015 (https:../../wiki/images/f/ff/CO485-2015-midterm15.pdf)
  • Bug in question 2(a): should be
  • Solutions (https:../../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 (https:../../wiki/images/8/82/CO485-2015-final10.pdf), 2013 (https:../../wiki/images/9/91/CO485-2015-final13.pdf), 2014 (https:../../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 (https:../../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 (https:../../wiki/images/3/3a/Co485-2015-s2.pdf)
• Assignment 3 (https:../../wiki/images/1/19/Co485-2015-a3.pdf) (due November 4).
  • Solutions (https:../../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 . Prove that the full Fujisaki-Okamoto transform is IND-CCA2. State any necessary assumptions.
  • Solutions (https:../../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 (https:../../wiki/images/1/13/Co485-2015-s5.pdf)