Princeton University
Computer Science Department

Computer Science 433
Cryptography

Boaz Barak

Spring 2010


News:
·final is online - click here for instructions.
· All students taking this course should join the mailing list.
· Mathematical background handout (including a "sneak preview" of exercises from Homework 1), (click here for LaTeX source)
Directory
Lecture notes | Reading | Admin

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


Administrative Information

Lectures: Mondays and Wednesdays 1:30pm-2:50pm, room: 105 in Computer Science building

Professor: Boaz Barak - 405 CS Building. Email: Phone: 609-981-4982 ?> (I prefer email)

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

Teaching Assistants: Sushant Sachdeva ( sachdeva@cs ) and Shi Li ( shili@cs )

course mailing list.

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

Homework assignment Due
HW1 (LaTeX source) February 10
HW2 (LaTeX source) February 17
HW3 (LaTeX source) February 24
HW4 (LaTeX source) March 3
HW5 (LaTeX source) March 10
HW6 (LaTeX source) March 24
HW7 (LaTeX source) March 31
HW8 (LaTeX source) April 7
HW9 (LaTeX source) April 14
HW10 (LaTeX source) April 21
HW11 (LaTeX source) April 28

I prefer you use LaTeX to write your solution. Here is a short guide for LaTex by Dave Xiao (you might want to look at the source files for the guide: latex-guide.tex and macros.tex).

Readings:

There is no textbook for this course. But the following books may be useful: Introduction to Modern Cryptography by Katz and Lindell. Foundations of Cryptography Volumes 1 and 2 by Oded Goldreich. Note that some of this material is online in the form of "fragments" of the book. We will also be using portions of the draft of the the book A graduate course in applied cryptography by Victor Shoup and Dan Boneh.

There are several lecture notes for cryptography courses on the web. In particular the notes of Trevisan, 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.

        February 2010 

 Sun  Mon  Tue  Wed  Thu  Fri  Sat

       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  
        March 2010 

 Sun  Mon  Tue  Wed  Thu  Fri  Sat

       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  
        April 2010 

 Sun  Mon  Tue  Wed  Thu  Fri  Sat

                      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  


Lecture 1: Monday, February 1, 2010
Overview of course, crypto history

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 (pptx) (Powerpoint (ppt))
Handout 1 - Mathematical Background
Excerpt from Katz-Lindell Book on Principles of Modern Cryptography (pages 18-27)

KL Book: Chapter 1 - introduction.

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

Mathematical proofs: Some links 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.
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. The Katz-Lindell excerpt explains some of the motivation behind this. See also pages 20-25 of Goldreich's book (Volume 1).


Lecture 2: Wednesday, February 3, 2010
Perfect secrecy and its limitations

Perfect Secrecy, the one-time pad. Limitations of perfect secrecy.
Lecture Outline

Trevisan Lecture 1 - intro one time pad KL Book: Chapter 2 - Perfectly secret encryption

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 the Turing machine. You might want to take a look at this chapter from my upcoming book with Sanjeev Arora.


Lecture 3: Monday, February 8, 2010
Computational model, computational security

Computational models and computational security.
Lecture Outline

Additional reading: Trevisan's lecture covers similar topics. You might want to look at the Boolean circuits and NP completeness chapter from my complexity book with Arora Some handouts from the last offer of this course: Powerpoint Slides (did not use these in class) computational models handout and figure. Computational complexity is covered in many places and in particular in Sipser's book and my book with Arora. 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.


Lecture 4: Wednesday, February 10, 2010
Canceled due to snow

Don't forget to do homework 2 due next week.

Lecture 5: Monday, February 15, 2010
Computational indistinguishability, pseudorandom generators

Computational indistinguishability, Pseudorandom generators, length extension.
Lecture Outline

KL Book: Chapter 3 - Private key encryption and pseudorandomness, see also Trevisan's lecture on this topic.

Additional reading: Please take a look at Section 6.4.2 of the Katz-Lindell book. You might also want to look at Goldreich's Treatment of pseudorandom generators (Volume I, pages 101-117).


Lecture 6: Wednesday, February 17, 2010
Length extension, Pseudorandom functions

Length extension of pseudorandom generators, pseudorandom functions.
Lecture outline (LaTeX source)

Reading: Boneh-Shoup sections 3.4, 4.6, Pages 215-220 from KL book, Trevisan lecture 14.

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: Monday, February 22, 2010
CPA security, pseudorandom permutations, block-ciphers, AES

Encryption schemes secure against Chosen-Plaintext Attack (CPA), Pseudorandom permutations, block ciphers and the AES.
Powerpoint slides (pptx) (Powerpoint slides (ppt).)

Reading: Boneh-Shoup chapters 4 and 5.

Additional reading:Goldreich Volume II (Chapter 5) contains an extensive discussion of the definitions of encryption schemes. See also KL book pages 82-93 and 221-225. (Sections 3.5, 3.6.1, 3.6.2 and 6.5). See also the following excerpt from Goldreich's book on the construction of PRF's from PRG's. (This excerpt is from a draft - see Goldreich Vol I for the updated version.)

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.

Food for thought: We'll next 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: Wednesday, February 24, 2010
The authentication problem, CCA security


Short recap of past lectures (powerpoint)
Lecture outline (LaTeX source)

KL book: Section 3.7 (pages 103-104),

Additional reading: 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. (These sources talk about public key encryption, but the underlying message is the same.)


Lecture 9: Monday, March 1, 2010
Message authentication codes

Message Authentication Codes (MAC). Order of authentication and encryption. PMAC and CMAC.
lecture outline (LaTeX source )

Reading: Boneh-Shoup Chapter 6, Sections 9.1-9.3.

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. The material about the order of encryption vs. authentication is from this CRYPTO 2001 paper by Hugo Krawczyk.


Lecture 10: Wednesday, March 3, 2010
MAC continued, hash and sign, pairwise independent hashing, random oracle model


lecture outline (LaTeX source )

Reading: Boneh-Shoup Chapter 7,8


Lecture 11: Monday, March 8, 2010
One way permutations and pseudorandom generators

One-way permutations and hard-core bits, with applications to pseudorandom generators and commitment schemes.
Lecture outline. (LaTEX source)
The Goldreich-Levin proof is taken from the chapter on cryptography in Arora Barak.

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.


Lecture 12: Wednesday, March 10, 2010
One way permutations, pseudorandom generators, commitment schemes (cont)


Lecture outline. (LaTEX source)

Reading for next time: Next week we'll start discussing number theory, in preparation for public key encryption schemes. Some resources for number theory include Chapter 7 and Appendix B of the KL book. There's also an excellent book of Victor Shoup (available freely on the web). The more you read of this book the better, however, I recommend you look in Chapter 1 (pages 1-10) and the first 5 pages of Chapter 8 (pages 180-184, not including exercise 8.1). Other 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, Chapter 10 (up to and including 10.4.1), first two pages of Chapter 11, Chapter 12 and Chapter 13. See also the mathematical background appendix from my book with Sanjeev Arora.


Lecture 13: Monday, March 22, 2010
Some basic number theory

Some basic number theory, including Chinese Remaindering Theorem, Fermat's little theorem, (poor man's) prime number theorem, primality testing and square roots modulo primes and composites.

Lecture outline. (LaTEX source)
Handout - reading for next class: Ralph Merkle's project proposal for Lance Hoffman's computer security course - CS244 at Berkeley - Fall 1974. To my knowledge this is the first time that the possibility of public key encryption was raised outside of the intelligence community.

Interestingly, apparently James Alice at the british intelligence agency GCHQ/CESG had ideas very similar to Merkle, in 1970, and Clifford Cocks there came up in 1973 with a number-theory based implementation similar to the RSA cryptosystem (and Malcolm Williamson came up with a protocol similar to the Diffie-Hellman key exchange). It seems that they didn't think of Merkle's protocol, Rabin's cryptosystem, and most importantly, digital signatures.

Additional reading: As mentioned above, Shoup's book is an excellent resource for computational number theory. You can also see the full fledged square root and primality testing algorithms in the following lecture by Shafi Goldwasser.


Lecture 14: Wednesday, March 24, 2010
Public key cryptography and Rabin encryption

Public Key Cryptography and the Rabin Encryption Scheme

Lecture outline. (LaTEX source)

Additional reading: Boneh-Shoup Chapter 10, KL Book Sections 10.1 , 10.2, 10.4, 10.7, 11.2. The "massaging" of the Rabin and RSA trapdoor permutations to the stronger form of the TDP Axiom is described in this note of Oded Goldreich, that also refers to Appendix C of Goldreich Vol II (see Section C.1).

Some more history: A very interesting review of the history of public key cryptography can be found in this interview of Martin Hellman.


Lecture 15: Monday, March 29, 2010
Signature schemes

Signature schemes: full domain hash, signatures from one-way functions + collision resistance.

Lecture outline. (LaTEX source)

Reading: Sections 13.1, 13.4, 14.5 of Boneh Shoup.

Additional reading: See also Chapter 12 of Katz-Lindell. 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 6.2.3.1 (Vol II). 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 Limpaa 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 16: Wednesday, March 31, 2010
CCA security for public key encryption

Security against Chosen Ciphertext Attack (CCA) for public key encryptions, random-oracle based constructions.
Lecture outline ((partial) LaTeX source)

Reading: Boneh Shoup chapter 12.

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 first 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.

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 17: Monday, April 5, 2010
Zero knowledge proofs, proofs of knowledge

Zero Knowledge Proofs.
Lecture outline (LaTeX source)

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

More reading: 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 18: Wednesday, April 7, 2010
Identification protocols, Sigma protocols, OR trick


Lecture outline (LaTeX source)

I didn't get to show the CCA secure encryption without random oracle, covered in Section 12.4.3.

Reading: Boneh-Shoup Chapter 18. For more reading on zero knowledge see notes in previous lecture.


Lecture 19: Monday, April 12, 2010
Homomorphic Encryption: definition and application to cloud computing, zero knowledge


Lecture outline (LaTeX source)

Additional reading: The original paper asking the question of fully homomorphic encryption is the 1979 paper On Data Banks and Privacy Homomorphisms by Rivest Adleman and Dertouzos, with the application to cloud computing (although they did not use this name...). At that time the notion of a probabilistic encryption was not standard, and one can view the negative results in this paper as showing that a homomorphic encryption must be probabilistic. The construction of a fully homomorphic encryption is in Craig Gentry's thesis. We will show in class the variant of van Dijk, Gentry, Halevi and Vaikuntanathan. Some more discussion on homomorphic encryption can be found in this (pre-Gentry) paper of Ishai and Paskin


Lecture 20: Wednesday, April 14, 2010
Homomorphic Encryption: application to multi-party secure computation


Lecture outline (LaTeX source)

Additional reading: Yehuda Lindell's webpage contains some good introductions on multiparty secure computation, including tutorial slides and a tutorial paper on using multiparty secure computation for privacy-preserving data mining. Also, the Wikipedia page on secure multiparty computation is surprisingly decent. See this paper on implementing multiparty secure computation for Danish sugar beet auctions for perhaps the state of the art in actually using these results. As is often the case, the implementation requires a lot of new protocols and ideas to actually make it practical. Helgar Lipmaa has a comprehensive collection of papers on secure multiparty computation. For an exposition of the "classical" (non homomorphic encryption based) protocols for 2 party secure computation see exposition by Lindell and Pinkas on Yao's Theorem (2-party honest but curious case) and exposition by Goldreich on GMW Theorem (k parties, malicious case).


Lecture 21: Monday, April 19, 2010
Homomorphic Encryption: construction of mildly homomorphic encryption


Lecture outline (LaTeX source) Note that after the lecture Sushant made a suggestion to simplify the scheme by slightly strengthening the assumption. The description of the simplified scheme appears in the notes for the next Lecture 22.

Lecture 22: Wednesday, April 21, 2010
Homomorphic Encryption: construction of fully homomorphic encryption


Lecture outline (LaTeX source)

Lecture 23: Monday, April 26, 2010
Quantum computing and cryptography

Quantum Computing and Cryptography
Slides (PowerPoint format)

For a good starting point on quantum computing, you can do far worse than explore Scott Aaronson's home page, see in particular his description of Shor's algorithm. See also the quantum chapter in my complexity book with Sanjeev Arora for more details on Simon's and Shor's algorithms, as well as Bell's experiment.


Lecture 24: Wednesday, April 28, 2010
Summary of course


Slides (PowerPoint format) (ppt format)

General links about cryptography

Some reading: An excellent discussion of provable security appears in this survey/position paper of Ivan Damgard. It refers also to issues raised in these 2004 and 2006 papers of Koblitz and Menezes, where they criticize proofs of security. In my view, some of the issues they raise are valid, though not novel, but the entire discussion is incomplete and rather misleading. See also this AMS Notices article by Koblitz and these responses (including one by me). Perhaps what bothers me most about these discussion is that they tend to focus too much on proofs of security, as opposed to precise definitions of security, whereas in my opinion the latter are even more fundamental to both the theory and practice of cryptography (although proofs are of course necessary to show that "crazy-sounding" definitions such as chosen-message secure signatures or chosen-ciphertext secure encryption can actually be satisfied).

Additional reading:


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.