Princeton University Computer Science Department

Computer Science 433 Cryptography Boaz Barak

Fall 2005

Course Summary

An introduction to modern cryptography with an emphasis on the fundamental ideas. We will survey both the basic information and complexity theoretic concepts as well as their (often surprising and counter-intuitive) applications.

Click on the lecture number for notes and/or slides, and links to additional reading material:

• Lecture 1 - Overview of crypto goals and history. Some classical ciphers and how they were broken. Outline of crypto 1970's "revolution".
• Lecture 2 - Perfect Secrecy, the one-time pad. Limitations of perfect secrecy.
• Lecture 3 - Statistical security and its limitations. Computational models - Boolean circuits. Complexity classes: P/poly, NP, P.
• Lecture 4 - Computational indistinguishability, Pseudorandom generators.
• Lecture 5 - Length extension of PRG, Encryption schemes secure against Chosen-Plaintext Attack (CPA).
• Lecture 6 - Pseudorandom functions, construction of CPA-secure encryption.
• Lecture 7 - Pseudorandom permutations, block ciphers and the AES.
• Lecture 8 - Message Authentication Codes (MACs)
• Lecture 9 - MACs II (order of encryption and authentication), Chosen Ciphertext Security (CCA) for private-key schemes.
• Lecture 10 - One-way permutations and hard-core bits, with applications to pseudorandom generators and commitment schemes.
• Lecture 11 - Some basic number theory.
• Lecture 12 - Public Key Cryptography and the Rabin Encryption Scheme
• Lecture 13 - Public key cryptography (continued), Diffie Hellman Key Exchange.
• Lecture 14 - Zero Knowledge Proofs.
• Lecture 15 - Zero Knowledge Proofs (continued).
• Lecture 16 - Signature schemes - part 1.
• Lecture 17 - Signature schemes (cont) and the random oracle model.
• Lecture 18 - Security against Chosen Ciphertext Attack (CCA) for public key encryptions, random-oracle based constructions.
• Lecture 19 - Authenticated key exchange and the SSL protocol , Bleichenbacher's attack.
• Lecture 20 - Secret sharing, visual cryptography, threshold signatures.
• Lecture 21 - Forward security, identity based encryption.
• Lecture 22 - Oblivious transfer, private information retrieval.
• Lecture 23 - Summary of the course.
• Lecture 24 - Quantum computing and cryptography.

Administrative Information

Lectures: Tuesday and Thursday 1:30pm-2:50pm, Room: Computer Science Room 102

Professor: Boaz Barak - 405 CS Building. Email: Phone: 258-0255 (I prefer email)

Undergraduate Coordinator: Donna O'Leary - 410 CS Building - 258-1746 doleary@cs.princeton.edu

Teaching Assistants: David Xiao ( dxiao@cs )

course mailing list.

Grading: 50% homework, 25% project, 25% take-home final. See syllabus for more details.

Course Information

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.

There are no formal prerequisites for the course, but I will assume that students are able to read and write mathematical proofs. In addition, familiarity with algorithms and basic probability theory will be helpful. I recommend that CS majors take this course after COS 226 and COS 341.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

Readings:

There are several lecture notes for cryptography courses on the web. In particular the notes of Vadhan, Bellare and Rogaway, Goldwasser and Bellare and Malkin will be useful.

Some good sources for the probability and complexity/algorithms backgrounds are:

• You should take a look at two short handouts by Luca Trevisan on probability and algebra.
• Appendix C of Introduction to Algorithms / Cormen, Leiserson, Rivest and Smith.
• Introduction to the Theory of Computation / Sipser.

A good source for computational number theory is A Computational Introduction to Number Theory and Algebra by Victor Shoup. Note that this book freely available on-line under the creative commons license. Another good book on this topic is A Concrete Introduction to Higher Algebra by Lindsay Childs.

Some other more application-oriented crypto books (note that these books take a much less careful approach to definitions and security proofs than we do in the course):

Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography.
Douglas R.  Stinson. Cryptography: Theory and Practice.
Bruce Schneier.  Applied Cryptography.
Ross Anderson Security Engineering

Lecture Notes and Handouts.

        September 2005 

 Sun  Mon  Tue  Wed  Thu  Fri  Sun

                      1    2    3  
  4    5    6    7    8    9   10  
 11   12   13   14   15   16   17  
 18   19   20   21   22   23   24  
 25   26   27   28   29   30  

        October 2005 

 Sun  Mon  Tue  Wed  Thu  Fri  Sun

                                1  
  2    3    4    5    6    7    8  
  9   10   11   12   13   14   15  
 16   17   18   19   20   21   22  
 23   24   25   26   27   28   29  
 30   31  

        November 2005 

 Sun  Mon  Tue  Wed  Thu  Fri  Sun

            1    2    3    4    5  
  6    7    8    9   10   11   12  
 13   14   15   16   17   18   19  
 20   21   22   23   24   25   26  
 27   28   29   30  

        December 2005 

 Sun  Mon  Tue  Wed  Thu  Fri  Sun

                      1    2    3  
  4    5    6    7    8    9   10  
 11   12   13   14   15   16   17  
 18   19   20   21   22   23   24  
 25   26   27   28   29   30   31  

Additional reading: You can find more information about historical ciphers on the web page Alex Biryukov's wonderful Course on Cryptanalysis.

Mathematical proofs: Some students asked me for material on reading, writing and coming up with mathematical proofs. Chapters 1 and 3 of the Lehman-Leighton notes of an MIT course can be useful. Some tips on mathematical writing in general and proofs in particular can be found in these few pages from Knuth, Larrabee, and Roberts. On a lighter and more general note, you might be interested to read Keith Devlin's musing about mathematical proofs.

Reading for next class: We'll start to use probability a lot (although only very basic things). The handout contains some references. In particular you might want to take a look at this short handout by Luca Trevisan.
We'll start also thinking about defining security for encryption schemes. Throughout this course the theme of such definitions will be rigor - mathematical precision and being conservative - making very strong demands on the security. In pages 20-25 of Goldreich's book (Volume 1) he gives a nice description of the motivation behind this approach.

Additional reading: Lecture 2 of Bellare's course discusses the issues in defining security for encryption schemes and perfect security. See also Section 6.4 in the Golwasser-Bellare lecture notes. The definition of perfect secrecy was first given by Shannon in this 1949 paper, but our discussion followed more closely the approach of Goldwasser and Micali who, when referring to the indistinguishability definition for encryption schemes, said: "A good disguise should not allow a mother to distinguish between her own children".

Reading for next class: Next class we'll discuss computational models such as Boolean circuits and Turing machines. You might want to take a look at pages 351-360 and 368-375 of Sipser's book. Also, I prepared a description of the computational models we use and the relationships between them. See also this picture

Additional reading: Computational complexity is covered in many places and in particular in Sipser's book. If you prefer PowerPoint slides you can look at Muli Safra's complexity course. In particular the first 5 presentations there (Introduction, Preliminaries, Reductions, Cook Theorem, and NP-complete Problems) roughly cover the material we discussed (and of course also some things we did not discuss). As I already mentioned, once we have an impossibility result, the right thing to do is to try to bypass it. This holds also for NP-completeness results where once a problem is NP-complete, and hence is probably not efficiently solvable, people try to approximately solve it (for example, if we can't color a graph in the minimum number of colors, try to color it within a factor of at most K times the minimum for some k.). This web site tracks the current approximation status of many problems. In many cases we can prove that it is NP-hard to even approximate some problems. For a good exposition of this, see Sanjeev Arora's thesis.

For next class: Next class we'll start use computational hardness for cryptography. There is no particular source to read, but you might want to think whether or not we can use worst case hardness for cryptography, and if not, what sort of hardness will we require.

Additional reading: You should look at Goldreich's