Princeton University Computer Science Department

Computer Science 433 Cryptography Boaz Barak

Fall 2007

Course Summary

Cryptography or "secret writing" has been around for about 4000 years, but was revolutionized in the last few decades. The first aspect of this revolution involved placing cryptography on more solid mathematical grounds, thus transforming it from an art to a science and showing a way to break out of the "invent-break-tweak" cycle that characterized crypto throughout history. The second aspect was extending cryptography to applications far beyond simple codes, including some paradoxical impossible-looking creatures such as public key cryptography , zero knowledge proofs, and playing poker over the phone.

This course will be an introduction to modern "post-revolutionary" cryptography with an emphasis on the fundamental ideas (as opposed to an emphasis on practical implementations). Among the topics covered will be private key and public key encryption schemes (including DES/AES and RSA), digital signatures, one-way functions, pseudo-random generators, zero-knowledge proofs, and security against active attacks (e.g., chosen ciphertext (CCA) security). As time permits, we may also cover more advanced topics such as the Secure Socket Layer (SSL/TLS) protocol and the attacks on it (Goldberg and Wagner, Bleichenbacher), secret sharing, two-party and multi-party secure computation, and quantum cryptography.

The main prerequisite for this course is ability to read, write (and perhaps enjoy!) mathematical proofs. In addition, familiarity with algorithms and basic probability theory will be helpful. No programming knowledge is needed. If you're interested in the course but are not sure you have sufficient background, or you have any other questions about the course, please contact me at

Lecture Notes and Handouts.

1. Overview of course, crypto history
2. Perfect secrecy and its limitations
3. Computational model, computational security
4. Computational indistinguishability, pseudorandom generators
5. CPA security, Pseudorandom functions
6. Pseudorandom permutations, block-ciphers, AES
7. The authentication problem, CCA security
8. Message authentication codes
9. One way permutations and pseudorandom generators, Goldreich-Levin Theorem
10. One way permutations, pseudorandom generators, commitment schemes (cont)
11. Some basic number theory (guest lecturer Benny Applebaum)
12. Public key cryptography and Rabin encryption
13. Signature schemes
14. CCA security for public key encryption
15. Zero knowledge proofs
16. Zero knowledge proofs (cont)
17. Forward security, identity-based encryption
18. Secret sharing, visual cryptography, threshold signatures
19. Oblivious transfer, Private information retrieval
20. Secure 2-party and multiparty computation
21. Electronic voting
22. Cramer-Shoup Cryptosystem
23. Quantum computing and cryptography
24. Course summary