CS 276 &mdash Cryptography &mdash Spring 2009

[general info]  [lecture notes] [midterm and project]

General Information

Instructor: Luca Trevisan, luca@eecs, 679 Soda Hall, Tel. 642 8006

Classes are Tuesday-Thursday, 4-5:30pm, 310 Soda

Office hours: Wednesdays, 2-3pm, or by appointment

About the course: an introduction to modern cryptography. We will talk about how to rigorously formalize the notion of security in various models, and how to use primitives having weak and plausible security properties (one-way permutations, trapdoor permutations) to build systems satisfying very strong, and sometimes seemingly outlandish, notions of security. The emphasis of the course will be on general principles, but, for concreteness, we shall also look at a number of examples and applications. Topics will include one-way functions, pseudorandomness, block ciphers, symmetric-key encryption, authentication, public-key cryptosystems, signatures, commitment schemes,  zero-knowledge proofs, advanced notions of security, and multi-party cryptographic protocols.

Coursework and grading: a homework will be posted every week or two. Homework problems will not be graded, but solving them will be very useful practice for the take-home midterm. Each student is required to scribe one lecture; the scribed notes will count for 20% of the grade. There will be a take-home midterm after spring break, which will count for 35% of the grade. A final project will count for 45% of the grade. The project will involve studying a paper or series of papers on an advanced subject not covered in class, writing a short report, and giving a 25-minute presentation in class. Two-people collaborations are possible, in which case the presentation will be 40 minutes. A project may be planned with a research problem in mind. Several such projects could become TCC 2010 papers. 


Other cryptography courses at Cornell, Harvard, Maryland, PrincetonUC San Diego, Weizmann (Goldreich), and Weizmann (Naor).

Classes and Lecture Notes

A basic knowledge of algebra and probability is a prerequisite for this class. As a refresher, here are some notes on algebra, and notes on probability.

For scribes: go here to find the template.tex and macros.tex files which are required to compile lecture notes. The file lecture00.tex gives some information on how to typeset the notes.


  1. 01/20 Introduction and overview. Some ancient history. One-time pad. Notes: [PDF] [HTML]
  2. 01/22 Message indistinguishability and semantic security. Notes: [PDF] [HTML]
  3. 01/27 Pseudorandom generators and one-time encryption. Notes: [PDF] [HTML]
  4. 01/29 RC4. Security for multiple encryptions. Stream ciphers. Notes: [PDF] [HTML]
  5. 02/03 Pseudorandom functions. CPA-secure encrpytion from pseudorandom fuctions. Notes: [PDF] [HTML]
  6. 02/05 Pseudorandom permutations, modes of encryption. Notes: [PDF] [HTML]
  7. 02/10 Message authentication. Notes: [PDF] [HTML]
  8. 02/12 CBC-MAC. CCA-secure encryption using MAC. Notes: [PDF] [HTML]
  9. 02/17 Cryptographic hash functions. Notes: [PDF] [HTML]
  10. 02/19 Practical constructions of block ciphers. Draft notes: [PDF] [HTML]
  11. 02/24 One-way functions, one-way permutations, and hard-core predicates. Notes: [PDF] [HTML]
  12. 02/26 The Goldreich-Levin Theorem. Notes: [PDF] [HTML]
  13. 03/03 Pseudorandom Generators. Notes: [PDF] [HTML]
  14. 03/05 Pseudorandom Functions from Pseudorandom Generators. Notes: [PDF] [HTML]
  15. 03/10 Pseudorandom Permutations from Pseudorandom Functions. Notes: [PDF] [HTML]
  16. 03/12 Pseudorandom Permutations from Pseudorandom Functions. Notes: [PDF] [HTML]
  17. 03/17 Public-Key Encryption. Notes: [PDF] [HTML]
  18. 03/19 Public-Key Encryption. Notes: [PDF] [HTML]
  19. 03/31 Public-Key Encryption. Notes: [PDF] [HTML]
  20. 04/02 Signature Schemes. Notes: [PDF] [HTML]
  21. 04/07 Signature Schemes. Notes: [PDF] [HTML]
  22. 04/09 Signature Schemes in the Random Oracle Model. Notes: [PDF] [HTML]
    04/14 No Class
  23. 04/16 Encryption in the random oracle model. Notes: [PDF] [HTML]
  24. 04/21 Zero Knowledge: definitions and graph isomorphism. Notes: [PDF] [HTML]
  25. 04/23 Zero Knowledge: quadratic residuosity. Notes: [PDF] [HTML]
  26. 04/28 Proofs of knowledge. Notes: [PDF] [HTML]
  27. 04/30 Commitment schemes and Zero Knowledge for NP. Notes: [PDF] [HTML]
  28. 05/05 Zero Knowledge for NP. Notes: [PDF] [HTML]


Problem Sets, Midterm and Project

The following problem sets will not be graded, and are not to be turned in. It is recommended that you try to solve them, to test what you learnt in class and to prepare for the midterm.
  1. Problem Set 1 refers to lectures 2-5
  2. Problem Set 2 refers to lectures 6-9
  3. Problem Set 3 refers to lectures 11-16


The MIDTERM is due by email before noon on Thursday, April 9. If possible, write your solution in LaTeX. Here is the LaTeX source of the midterm, which you may find helpful. Here is a running list of corrections from the originally posted version. The files are accessible only from within the berkeley.edu domain. I can send you a copy by email if you are having trouble.


The project will be due by Tuesday, May 5, at noon. The PROJECTS PAGE is under construction.