Foundations of Cryptography 1, Fall 2016

Supplementary Material

  • Foundations of Cryptography, Oded Goldreich
    Draft is available online. Several copies available to borrow (courtesy of Oded).
  • Introduction to Modern Cryptography, Jonathan Katz and Yehuda Lindell
  • Non-Uniform Computation
    Foundations of Cryptography  Volume 1, Oded Goldreich, Sec 1.3.3. See also the draft

Problem Sets

Lectures

  • Lecture 1. Nov 9, 2016
    Introduction, perfect security and the one-time pad.
    Reading: Katz-Lindell chapters 1,2
  • Lecture 2. Nov 16, 2016
    Computationally secure cryptography, private-key encryption, indistinguishable and semantically secure encryptions.
    Reading: Katz-Lindell chapters 3.1, 3.2
  • Lecture 3. Nov 23, 2016
    Non-uniform computation, indistinguishable encryptions imply semantic security, pseudo-random generators and their application to constructing encryption schemes.
    Reading: Goldreich chapter 5.2.3 (see also 5.2.1, 5.2.2), Katz-Lindell chapter 3.3
  • Lecture 4. Nov 30, 2016
    Increasing the stretch of pseudo-random generators, hybrid arguments.
    Reading: Goldreich 3.2, 3.3.1, 3.3.2
  • Lecture 5. Dec 7, 2016
    Multi-message private-key encryption, stateful encryption using PRGs, pseudo-random functions (PRFs), stateless encryption using PRFs.
    Adaptive attacks: chosen-plaintext security and chosen-ciphertext security.

    Reading: Goldreich 3.6.1, 5.2.4, 5.3.1, 5.3.2, 5.3.3, 5.4.1, 5.4.3, 5.4.4
  • Lecture 6. Dec 14, 2016
    PRF construction, one-way functions: definition and motivation.
    Reading: Goldreich 3.6.2, 2.1, 2.2.1
  • Lecture 7. Dec 21, 2016
    Weak one-way functions (OWFs), from weak OWFs to strong OWFs.
    Reading:  Goldreich 2.2.2-2.2.4, 2.3
  • Lecture 8. Dec 28, 2016
    Weak OWFs to Strong OWFs (wrap-up), one-way permutations, hardcore predicates, Goldreich-Levin Theorem: statement and warm-up for proof.
    Reading: Goldreich 2.3, 2.5.1, 2.5.2 “motivating discussion”
  • Lecture 9. Jan 4, 2017
    Goldreich-Levin Theorem: full proof.
    Reading: Goldreich 2.5.2 (full proof)
  • Lecture 10. Jan 11, 2017
    Message authentication codes (MACs).
    Reading: Katz-Lindell 4.1, 4.2, 4.3
  • *No lecture on Jan 18, 2017*
  • Lecture 11. Jan 25, 2017
    Digital signature schemes.
    Reading: Katz-Lindell 12.1, 12.2, 12.3, 12.6.1, 12.6.2
    For a full specification of the multi-message signature scheme, you can also read Lindell’s lecture notes, section 12.3
  • Lecture 12. Feb 1, 2017
    Interactive Proofs and Zero-Knowledge.
    Reading: Goldreich 4.1, 4.2.1, 4.2.2, 4.3.1, 4.3.2
  • Lecture 13. Feb 8, 2017
    Zero-Knowledge Proofs for NP, Composition, Summary
    Reading: Goldreich 4.4.1, 4.4.2, 4.4.3 (optional), 4.3.3, 4.3.4
    For a full proof of the zero-knowledge property for the three-coloring protocol, you can also read Lindell’s lecture notes, section 7.2