CS 8803FC - Foundations of Cryptography. Spring 2008

From Theory
Jump to: navigation, search
CryptoBook.jpg Goldreich1.jpg Goldreich2.jpg

Course Info

Teacher: Yael Tauman Kalai

Time: Tues/Thu 12:05-1:25pm (First Meeting Jan 8th)

NEW location: Klaus 3402 (From Thursday Feb. 14)

Summary: Cryptography (or "secret writing") has been around for about 4000 years, but the study of modern cryptography started only in the last few decades. Modern cryptography has revolutionized cryptography in two ways: First, it has placed cryptography on more solid mathematical grounds, thus transforming it from an art to a science. Second, it has extended cryptography to applications far beyond simple codes, including some paradoxical impossible-looking creatures such as digital signatures and zero-knowledge proofs.

This is an introductory graduate-level theory course on modern cryptography, with an emphasis on the fundamental ideas. Topics include: private-key and public-key encryption schemes, one-way functions, pseudo-random generators, pseudo-random functions, and zero-knowledge proofs. As time permits we may also cover more advanced topics such as two-party and multi-party secure computation.

Suggested reading: This class will follow the class given by Rafael Pass at Cornell http://www.cs.cornell.edu/courses/cs687/2006fa, and by Abhi Shelat at the University of Virginia http://www.cs.virginia.edu/~shelat/651/www/index.html. In particular, we will use their lecture notes (pdf lecture notes). Thanks Rafael and Abhi!

The recommended textbooks for this course are Introduction to Modern Cryptography (Chapman & Hall) by Jonathan Katz, Yehuda Lindell [1], and Foundations of Cryptography Vol. 1 and 2 by Oded Goldreich[2]. The latter is a very comprehensive treatment of the theoretical foundations of cryptography, and is a great referrence for those interested in understanding the material in greater depth.

Grading: Homework assignments 50% and a final exam 50%.

Grading policy: You may collaborate with other students on the homework but you must submit your own individually written solution and you must identify your collaborators. If you make use of any other external source, you must acknowledge it. You are not allowed to submit a problem solution which you cannot explain orally.


1. FC08 Assignment 1 Due 2/7/08.

2. FC08 Assignment 2 Due 2/28/08.

3. FC08 Assignment 3 Due 3/13/08.

4. FC08 Midterm Assignment (sent by email only) Due 4/8/08.

5. FC08 Assignment 5 Due 4/24/08.

Syllabus (tentative)

  • Introduction
    • Introduction & overview
    • Information theoretic security
      • Shannon's definition of security. One-time Pads. Limitations of the information theoretic approach.
  • Computational hardness and one-wayness
    • Efficient Computation and computationally bounded adversaries
    • One-way functions (OWFs)
      • Strong OWFs and weak OWFs
      • Hardness amplification: weak OWFs imply srong OWFs link
      • Collection of OWFs
    • Computational number theory
      • Modular arithmetics
      • Euclid's algorithm
      • Groups: <math>Z_n</math> and <math>Z_n^*</math>
      • Euler's theorem and Fermat's little theorem
      • Density of primes
      • Miller-Rabin primality test
    • Constructions of OWFs
      • Based on Factoring Assumption, Discrete Log Assumption, and RSA Assumption
    • Collection of trapdoor permutation
      • Construction based on RSA Assumption
    • Hard-core predicate for any one-way function link
  • Indistinguishability and pseudo-randomness
    • Computational indistinguishability
    • Pseudo-random generators
    • Pseudo-random functions (PRF)
    • PRFs and private-key encryption
    • Public-key encryption
  • Knowledge
    • Interactive proofs
    • Zero-knowledge proofs
    • Proofs of knowledge
    • Witness indistinguishable proofs
  • Authentication
    • Message Authentication Codes
    • Digital signatures
    • Hash functions

  • Computing on secret inputs
    • Secret Sharing
    • Oblivious transfer
    • Secure computation