|
COS 433/MAT 473
Cryptography
|
Fall 2013
|
· IMPORTANT: All students taking this course should join the mailing list by clicking here and filling in your email address (you will not be added automatically just by registering to the course!). All announcements will be posted to this mailing list.
Administrative
Lectures: Mondays and Wednesdays 1:30pm-2:50pm, room: McCormick 101
Professor: Zeev Dvir (follow link for contact information)
Office Hours: By appointment.
Teaching Assistants:
Rafael Oliveira (rmo@cs.princeton.edu), COS 417. Office hours Tue 6 - 7pm.
Aman Dhesi (adhesi@cs.princeton.edu), COS 103B. Office hours Mon 6-7pm (tentative).
Grading: 50% homework, 50% take-home final.
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).
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.
Reading:
A good source for reading are these lecture notes by Salil Vadhan for a similar course taught at Harvard.
There is no required textbook for the course. The book Introduction to Modern Cryptography by Katz and Lindell contains most of the material and is recommended for the level of this course. The CS library should have several copies on reserve for this class.
Another good source for reading (more advanced) is
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.
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
Homework Assignments
It is required that you use LaTeX to write your solutions. 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). Another source for sample LaTex files is the website for Crypto Spring 2010.
Collaboration Policy
Students are encouraged to discuss the course material and the homework problems with each other in small groups (2-3 people). Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem. In addition, each person must write up their solutions independently, and these write-ups should not be checked against each other or passed around.
Late Submissions
Submission that are at most 2 days late will be graded with a 10pt penalty. Later submissions will not be accepted.
Lecture Notes and Handouts.
9/11/13 - Lecture 1:
-Introduction. Basic scenario of encryption. Substitution cipher. Classical vs. Modern crypto. Goals of theoretical crypto. Suggested reading: Chapter one of [KL] (available online). Lecture notes by S. Vadhan.
9/16/13 - Lecture 2:
- Review of discrete probability. Probability spaces, events, random variables, independence. Markov, Chebyshev, Chernoff. Union bound. Suggested reading: Notes by Boaz Barak. Lecture notes by S. Vadhan.
9/18/13 - Lecture 3:
- We saw a definition of a private-key encryption scheme. We defined the notion of perfect indistinguishability and saw that the one-time pad is perfectly secure. We also proved that any perfectly secure encryption scheme has a key space that is as large as the message space. We continued to define Statistical distance and statistical indistinguishability.
- Suggested reading: Lecture notes by S. Vadhan.
9/23/13 - Lecture 4:
- Big 'O' notation. Review of algorithms and complexity. Modeling the users of the system as probabilistic polynomial time (PPT) algorithms. Modeling the adversary as a non-uniform PPT algorithm. Suggested reading: Lecture notes by S. Vadhan.
9/25/13 - Lecture 5:
- Computational security. Definition of computationally indistinguishable encryptions. Guessing indistinguishability. Concrete security. Semantic security. Suggested reading: Lecture notes by S. Vadhan. For a more advanced treatment of the definitions we saw and a proof of the equivalence of semantic security see Katz-Lindell or Goldreich's book (Vol II, sec 5.2).
9/30/13 - Lecture 6:
- Pseudorandom Generators (PRG). Computational security of pseudorandom one-time pad. Proof of security by reducing a hypothetical adversary to another adversary. Definition of One way functions. Factoring assumption. Suggested reading: Lecture notes on PRG's and on OWF's by S. Vadhan. These notes by B. Barak cover everything we discussed on PRG's and computational indistinguishability as well as some practical candidates for PRGs (you can skip the length extension theorem, we will prove it later on in the course).