Princeton University
Computer Science Department

Computer Science 433

Boaz Barak

Fall 2005

· Take-home final is now available - deadline is January 17th, 2006 12:00pm (noon)
· Deadline for course project - January 13th, 2006 1:30pm.

Latest Lecture | Admin | Course Info | Reading | Lecture notes

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:

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

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

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.

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


There is no single official textbook for this course. However, some of the lectures will follow Oded Goldreich's book Foundations of Cryptography Volumes 1 and 2. Note that some of this material is online in the form of "fragments" of the book.

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:

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

  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  

Lecture 1: Thursday, September 15, 2005
Overview of crypto goals and history. Some classical ciphers and how they were broken. Outline of crypto 1970's "revolution". Admin info about the course.
Powerpoint Slides
Handout 1 - Probability (LaTeX source) - solutions due Tuesday, September 20. Including correction of statement of Chebychev bound (Sep 18)
We prefer that you use LaTeX to write your solution. Dave wrote a short guide for LaTex (you might want to look at the source files for the guide: latex-guide.tex and macros.tex).

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.

Lecture 2: Tuesday, September 20, 2005
Perfect Secrecy, the one-time pad. Limitations of perfect secrecy.
Lecture Outline
Powerpoint Slides (partial, did not use these in class)
Handout 2 - Perfect and statistical secrecy, computational models (LaTeX source). Solutions due Tuesday, September 27.
I also handed out a summary of the term project. Note that by Thursday, September 29th 1:30pm you should send me an email with the members of your group and rough description of the application.

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

Lecture 3: Thursday, September 22, 2005
Statistical security and its limitations. Computational models - Boolean circuits. Complexity classes: P/poly, NP, P.
Lecture Outline
Powerpoint Slides (partial, did not use these in class)
computational models handout and figure.

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.

Lecture 4: Tuesday, September 27, 2005
Computational indistinguishability, Pseudorandom generators.
Lecture Outline
Handout (Latex Source) - Due October 11th
Powerpoint Slides (partial, did not use these in class)

Additional reading: You should look at Goldreich's Treatment of pseudorandom generators (Volume I, pages 101-117). He uses somewhat different notations than we do (in particular working with the asymptotic definition of computational indistinguishability and pseudorandomness, and using a uniform model of computation rather than Boolean circuits).

Lecture 5: Thursday, September 29, 2005
Length extension of PRG, Encryption schemes secure against Chosen-Plaintext Attack (CPA).
Lecture outline

Additional reading & reading for next class: I believe it is very instructive to read and compare Goldreich's proof of PRG length extension (Volume I, pages 114-117) to ours. Goldreich Volume II (Chapter 5) contains an extensive discussion of the definitions of encryption schemes.

Lecture 6: Tuesday, October 4, 2005
Pseudorandom functions, construction of CPA-secure encryption.
Lecture outline
Homework (Latex Source) - Due October 11

Additional reading: Pseudorandom functions were defined and constructed by Goldreich, Goldwasser, and Micali - (see this page for the paper, containing also the full proof). As mentioned, there are other more efficient candidate constructions, including HMAC by Bellare, Canetti and Krawczyk and a factoring-based PRF by Naor, Reingold and Rosen.

Lecture 7: Thursday, October 6, 2005
Pseudorandom permutations, block ciphers and the AES.
Powerpoint slides.

Additional reading: You should take a look at the Bellare-Rogaway chapter on pseudorandom functions and permutations. It does not cover exactly the same material we do (which is why it would be especially worth your while to look at it). Pseudorandom permutations, and their construction based on pseudorandom functions is covered in Goldreich Vol I (link is for the older web version, see there section 3.7 page 114).

A lot more information on the AES and other block ciphers can be found on the web page for Eli Biham's modern cryptology course. In particular, this lecture covers block ciphers. See The AES Lounge for more information about the AES, its security and implementations.

If you are interested in the principles behind the design and attack of block ciphers, see this tutorial by Howard Heys and this course by David Wagner.

Finally if the skipjack/clipper story whetted your appetite for crypto-conspiracies you might want to look at this site.

For next week: Next week we'll begin to talk about the goal of integrity. There's nothing in particular you should read but try to think of the following questions:

Lecture 8: Tuesday, October 11, 2005
Message Authentication Codes (MACs)
Lecture outline
Short recap of past lectures (powerpoint)
Handout (LaTeX source) - due October 18th, 2005
Project specification document - instructions

Additional reading: Lectures 9 and 10 in David Wagner's cryptography course discuss MACs, including examples of real-world protocols that can be attacked due to lack of MACs.

Lecture 9: Thursday, October 13, 2005
MACs II, Chosen Ciphertext Security (CCA) for private-key schemes.
Lecture outline

Additional reading: The material about the order of encryption vs. authentication is from this CRYPTO 2001 paper by Hugo Krawczyk. See this expository paper by Victor Shoup for more on the motivation behind chosen ciphertext security. You can find here the CRYPTO 98 paper of Daniel Bleichenbacher that attacked the SSL protocol, mainly using the fact that the underlying encryption scheme was not CCA-secure.

Reading for next class: Next week (probably on Thursday) we'll start discussing number theory, in preparation for public key encryption schemes. Please take a look at Shoup's book (available freely on the web). The more you read of this book the better, however, please read at least Chapter 1 (pages 1-10). Particularly relevant parts of the rest of the book are: Chapter 2 (up to and including Section 2.5), first 2 pages of Chapter 7, first 5 pages of Chapter 8, Chapter 10 (up to and including 10.4.1), first two pages of Chapter 11, Chapter 12 and Chapter 13.

Lecture 10: Tuesday, October 18, 2005
One-way permutations and hard-core bits, with applications to pseudorandom generators and commitment schemes.
Lecture outline
Homework (LaTeX source) - due October 25th, 2005.
Step by step solution for exercise 1 of handout 4

Additional reading: One-way permutations and the hard-core bits are covered extensively in Goldreich Volume 1 (although it is perhaps too extensive for our purposes). Vadhan's lecture notes cover one-way functions, Commitment schemes and hardcore bits (see also lecture 10 and 11 there). Luca Trevisan's lecture notes on pseudorandomness have a nice presentation of the proof of the Goldreich-Levin theorem. Note: You might want to look at these sources after you tried to tackle Exercise 1 on your own.

In many places there is an emphasis not so much on one way permutations but on one way functions. One-way functions are a generalization of one-way permutations in the sense that every one-way permutation is a one-way function but not necessarily vice versa. The definition is the natural way you'd generalize the definition one-way permutations to the case where the function f() may not be one-to-one: since for a given y there may be many x's such that y=f(x), adversary is successful if it manages to find one of them.

Reading for Thursday: In addition to Chapter 1 (pages 1-10) please also read the first 5 pages of Chapter 8 in Shoup's book (pages 180-184, not including exercise 8.1).

Lecture 11: Thursday, October 20, 2005
Some basic number theory.
Lecture outline

Additional reading: Please take a look at the notes for this lecture by Shafi Goldwasser. As mentioned above, Shoup's book is an excellent resource for computational number theory.

Lecture 12: Tuesday, October 25, 2005
Public Key Cryptography and the Rabin Encryption Scheme
Guest lecturer Tal Rabin - IBM T.J. Watson

Lecture 13: Thursday, October 27, 2005
Public key cryptography (continued), Diffie Hellman Key Exchange.
Lecture outline
Homework 6 (LaTeX source) -- due November 8th, 2005.

Additional reading: There are many sources for public key encryption. I particularly recommend the Goldwasser and Bellare. Dan Boneh has an excellent survey on the Decisional Diffie Hellman (DDH) assumption we mentioned in class.

Lecture 14: Tuesday, November 8, 2005
Zero Knowledge Proofs.
Lecture outline
Homework (LaTeX source) -- due November 15th, 2005.

Additional readings: One of the best non-technical explanation of zero knowledge appears in this paper by Naor, Naor and Reingold published in the prestigious Journal of Craptology.

The most extensive treatment of Zero Knowledge is in Goldreich, Vol I, Chapter 3 (see also fragments on the web). For a shorter version, see chapter 4 of foundations of cryptography -- a primer). Goldreich also has tutorial on zero knowledge including the basic notions and more recent developments as well. protocol QR I described in class is also described in these UCB computer security lecture notes.

You can find on line the original paper of Goldwasser, Micali and Rackoff presenting zero knowledge. Zero knowledge is also the topic of many dissertations (including my own), I particularly recommended Uri Feige's thesis

Lecture 15: Thursday, November 10, 2005
Zero Knowledge Proofs (continued).
Lecture outline

Additional reading: I strongly recommend you look at the following lecture notes of an MIT course by Silvio Micali (one of the inventors of zero knowledge). Lectures 1 to 5 cover the material we talked about in class. If you are interested in more about zero knowledge then the rest of the lectures are a good place to start. A good overview of the material is in pages 1 to 17 of Goldreich's tutorial on zero knowledge. For full proofs see Goldreich's book or the fragments on the web. In particular, reduction of error by sequential composition is covered in section 4.3.4 of the fragments, and the protocol for 3-coloring is covered in section 4.4.

If you like slides, you can see some of this material in PowerPoint format from Muli Safra's course (see also these slides from Ely Porat).

Lecture 16: Tuesday, November 15, 2005
Signature schemes - part 1.
Lecture outline
Homework (LaTeX source) -- due November 22nd, 2005.

Additional reading: Fuller exposition and proofs for this material can be found in Chapter 6 of Goldreich's book (Vol II) or in the fragments on the web.The Goldwasser-Micali-Rivest factoring based hash function is obtained through the intermediate notion of claw-free permutations. This construction is described somewhat tersely in the Golswasser-Bellare notes and with a bit more detail in Goldreich's sections 2.4.5 (Vol I) and (Vol II),

Lecture 17: Thursday, November 17, 2005
Signature schemes (cont) and the random oracle model.
Lecture outline

Additional reading: The paper of Bellare and Rogaway suggesting the random oracle model can be found here. One of the most powerful critiques of this model is in this paper by Canetti, Goldreich and Halevi (be sure to look at the authors' opinions at the end). Helger Lipmaa collected some links related to the random oracle model.

As mentioned in class, Bellare and Rogaway built on an earlier work of Fiat and Shamir that gave a different construction for signature and identification schemes using a "crazy" hash function based on zero knowledge proofs. The Bellare-Rogaway signature scheme with a tighter security proof can be found here.

Lecture 18: Tuesday, November 22, 2005
Security against Chosen Ciphertext Attack (CCA) for public key encryptions, random-oracle based constructions.
Lecture outline
Homework (LaTeX source) -- due November 29th, 2005.
The homework mentions the following papers of Shoup and Boneh.

Additional reading: Chosen ciphertext security was defined by Rackoff and Simon. As mentioned in the notes for lecture 9, Victor Shoup has a very nice expository paper about this concept. The first construction that was proven to be chosen-ciphertext secure was given in this paper of Dolev, Dwork and Naor. However, this construction is quite complicated and inefficient. Perhaps the simplest (although rather inefficient) construction and analysis of a "random-oracle free" CCA-secure encryption is given in this paper by Lindell. Both constructions use an ingredient that we did not talk about in class (non-interactive zero knowledge proofs) but is described in Goldreich's book (Vol I).

The scheme we presented in class was taken from the original random-oracle paper by Bellare and Rogaway. An efficient encryption scheme with a proof of "almost CCA security" in the random oracle model is the OAEP scheme of Bellare and Rogaway. However, in this paper by Shoup he shows some "holes" in that proof and gives a different random-oracle based construction. Perhaps the simplest and most efficient encryption that has a proof of CCA security in the random oracle model is this one by Dan Boneh.

In this wonderful paper of Cramer and Shoup they present an efficient encryption scheme that has a "real" (no random oracles) proof of CCA security based on the DDH assumption.

Even if a scheme is proven to be CCA secure, this only implies real world security if the real world adversary does not have access to additional information from observing say the time it takes servers to answer queries or other such things - see this paper for a demonstration of this issue.

Lecture 19: Tuesday, November 29, 2005
Authenticated key exchange and the SSL protocol, Bleichenbacher's attack.
Lecture outline
Homework (LaTeX source) -- due December 6th, 2005.

Additional reading: See Bleichenbacher's paper for more information about his attack on RSA as used in the SSL protocol. Some related attacks can be found here. As mentioned in the reading for the previous lecture, even when using assumed CCA secure schemes, an adversary may use timing and/or error message information to attack a scheme, as demonstrated in this CRYPTO 2001 paper by Manger.

The SSL protocol is also described in these notes by Lindell. Some attacks on SSL V3.0 are described in this paper by Schneier and Wagner (although it is pre-Bleichenbacher, and so does not include many strong attacks, to quote from a summary of a talk by Wagner on this work: "In general, this analysis was informal, not formal, meaning that it can only illustrate flaws in the protocol, not prove that it's correct."). The attack on the pseudorandom generator used by Netscape was given in this paper by Goldberg and Wagner.

Lecture 20: Thursday, December 1, 2005
Secret sharing, visual cryptography, threshold signatures.
Lecture outline

Additional reading: You can find more about PGP key reconstruction on the PGP user guide. Here's a nice puzzle about visual cryptography. You can find the relevant papers from Moni Naor's web page. See also Doug Stinson's page on visual cryptogeaphy. You can find a nice and relatively simple threshold RSA signature scheme in this paper by Shoup. See this paper of Tal Rabin on how to convert the scheme we saw in class to a general threshold, robust, and proactive scheme. I was actually once involved in writing Java implementation of proactively secure protocols.

Lecture 21: Tuesday, December 6, 2005
Forward security, identity based encryption.
Lecture outline
Homework (LaTeX source) -- due December 13th, 2005.

Additional reading: Dan Boneh's group has a web page on Identity Based Encryption where you can find the original Boneh-Franklin paper and also download encrypted email software based on IBE. The forward-secure encryption scheme given in class is from this note by Canetti and Halevi which is a simplification of the construction of this paper by Canetti, Halevi and Katz (the latter however is better in the sense that it does not need a large storage by the sender and also does not use the random oracle model). See this paper by Bellare and Yee for a treatment of forward security for private key primitives.

Lecture 22: Thursday, December 8, 2005
Oblivious transfer, private information retrieval.
Lecture outline

Additional reading: Some web resources on oblivious transfer are this page by Benn Lynn and this page by Helger Lipmaa. A full exposition with constructions and proofs of oblivious transfer and secure function evaluation can be found in Goldreich's book (Vol II). This paper of Kushilevitz and Ostrovsky gave the first computationally secure PIR with single server and sublinear communication. It also discusses some possible applications for PIR. Amos Beimel has a webpage on private information retrieval. This project is about obtaining practical PIR protocols. See this paper and the announcement for this workshop for some information on the connections between PIR protocols and other objects. See also this survey on private information retrieval by Gasarch.

Lecture 23: Tuesday, December 13, 2005
Summary of course.

Additional reading:

Lecture 24: Thursday, December 15, 2005
Quantum Computing and Cryptography
Slides (PowerPoint format)

Honor Code for this class

Collaborating with your classmates on assignments is OK and even encouraged. You must, however, list your collaborators for each problem. The assignment questions have been carefully selected for their pedagogical value and may be similar to questions on problem sets from past offerings of this course or courses at other universities. Using any preexisting solutions from these other sources is strictly prohibited.