CS 8803TFC - Theoretical Foundations of Cryptography, Spring 2010

From Theory
Revision as of 17:51, 27 January 2011 by Cpeikert (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
CryptoBook.jpg Goldreich1.jpg Goldreich2.jpg

Course Information

Instructor: Chris Peikert

Time: Tue/Thu 9:35-10:55am (First meeting: Jan 12th)

Location: College of Computing building, room 53.

Summary: Cryptography, or "secret writing," is nearly as old as written communication itself. Yet only over the past few decades has it grown from a "black art" into a true science with rigorous mathematical foundations and methodologies. These have taken cryptography far beyond its roots in simple secret codes, to a discipline with far-reaching influence on computing as a whole.

This class is a graduate-level, theory-oriented introduction to the foundations of modern cryptography. The emphasis is on essential concepts, precise models and definitions, and proof techniques. Topics include: one-way functions and related complexity assumptions, pseudorandomness, public-key and identity-based crypto, zero knowledge and commitment, and connections to diverse areas of computer science. As time permits, we may also touch upon specialized topic areas such as secure multiparty computation, private information retrieval, or lattice-based cryptography.

For more information and course policies, see the course information and syllabus handout.


Handouts and Lecture Notes

  • Lecture 1: Overview, Perfect Secrecy
    • Supplementary reading: Section 1.3 of Pass-shelat

Computational Hardness

  • Lecture 2: Limits of Perfect Secrecy, Computational Hardness
    • Supplementary reading: Sections 2.1-2.2 of Pass-shelat
  • Lecture 3: Candidate OWFs, Hardness Amplification
    • Supplementary reading: Sections 2.3-2.5 of Pass-shelat
  • Lecture 4: Number Theory, OWF Variants
    • Supplementary reading: Section 2.6-2.7 of Pass-shelat

Indistinguishability and Pseudorandomness

  • Lecture 5: Indistinguishability, Pseudorandom Generators
    • Supplementary reading: Sections 3-3.3 of Pass-shelat
  • Lecture 6: Expanding PRGs, Blum-Micali
    • Supplementary reading: Sections 3.3-3.4.1 of Pass-shelat
  • Lecture 8: Pseudorandom Functions
    • Supplementary reading: Section 3.8 of Pass-shelat
  • Lecture 9: Symmetric Encryption
    • Supplementary reading: Sections 3.5-3.7, 3.9 of Pass-shelat
  • Lecture 10: Asymmetric Encryption
    • Supplementary reading: Sections 3.10-3.11 of Pass-shelat


  • Lecture 11: Message Authentication
    • Supplementary reading: Sections 5-5.2 of Pass-shelat
  • Lecture 12: CCA Security, Digital Signatures
    • Supplementary reading: Sections 5.3-5.4 of Pass-shelat
  • Lecture 13: Digital Signatures
    • Supplementary reading: Sections 5.5-5.7 of Pass-shelat
  • Lecture 14: Random Oracle Signatures
    • Supplementary reading: Sections 5.8 of Pass-shelat

Zero Knowledge

  • Lecture 15: Zero Knowledge, Interactive Proofs
    • Supplementary reading: Sections 4-4.5 of Pass-shelat
  • Lecture 16: ZK Proofs
    • Supplementary reading: Sections 4.5-4.6 of Pass-shelat
  • Lecture 17: ZK for NP
    • Supplementary reading: Section 4.7 of Pass-shelat

Special Topics

Useful Links


Previous iterations of this course: