Topic outline

  • Foundations Materials

    • 01 Lecture Folder

      Lecture 1:

      • High-level concepts of pre-image resistance (PRE), 2nd pre-image (2PRE) resistance and collision-resistance (CR)
      • Definition of min-entropy, 
      • Definition of PRE, 2PRE, CR
      • Definition of extractor
      • Relations: CR => 2PRE => PRE
      • Discussion of separations (to be discussed in the subsequent weeks)

      The lecture video is split into 4 parts to encourage taking breaks when watching it, here are the links: Part 1, Part 2, Part 3, Part 4 .

      Quiz deadline: Tuesday, January 9, 10:00

      You can find the lecture notes in the folder below.

      Update on January 8, 9:51 to 01-lecture.pdf: I updated the lecture notes to say that a distribution is high-entropy if its min-entropy is at least lambda+1. Before, it just required superlogarithmic, but that is not so convenient for proving implications...

      Update on January 10, 11:20 to 01-lecture.pdf: I changed lambda+1 to 2lambda, because I found a counterexample (see Zulip), where h(s,.) is still injective on a large fraction of the domain.

    • 02 Lecture Folder
      • Black-box reduction
      • Black-box separation
      • Apply this concept to showing that it is impossible to build a CR from a OWF in a black-box way.
      • Simon's separation result to separate CR from OWF
      • Applications of hash-functions to password-authenticated key exchange.

      There are three video lectures: Part 1, Part 2, Part 3.

      Pihla also made a brief lecture about statistical indistinguishability: Video

      We will discuss the content of the videos on January 15, 2024, at 10:15. Deadline for the embedded quizzes is January 15, 10:00. One question we will discuss is if / why modeling the one-way function as a random function is meaningful. In the folder, there are the notes which I took during the lecture.

    • 03 Lecture Folder

      We revisit Simon's separation, this time via an incompressibility argument. This is part A. Part B will take place next week. Below, I include Pihla's notes as well as a proof tree of Pihla's proof. Here are the links to the lecture videos: Part 1, Part 2

    • 04 Lecture Folder

      Compression version of Simon's oracle separation (continued).

      Videos: Part 1, Part 2

      Below are some notes.

    • 05 Lecture Folder

      •  Statistical distance

      •  Collision probability

      • 2-universal hash-functions

      •  Leftover hash-lemma

      Lecture Video

      Below, you find lecture notes as well as scribbles which I made during the video lecture.

    • 06 Lecture Folder
      • "Every" computationally secure cryptographic primitive implies one-way functions." is a conceptual result proven by Impagliazzo and Luby and we discuss it in this lecture.
      • Definition of computational distance
      • Definition of distributional one-way functions
      • Proof that the existance of two efficiently sampleable distributions with a gap between statistical and computational distance implies the existence of one-way functions.

      Link to the lecture: Video

      Below are lecture scribbles --- the lecture notes cover the statistical bounds.

    • 07 Lecture Folder

      This lecture introduces hybrid proofs on the example of PRG length-extension. Below are the lecture notes and lecture scribbles. Here are the links to the lecture videos:

      Part 1, Part 2 and Part 3.

    • 08 Lecture Folder
      In lecture 8, we show that PRGs imply PRFs via the famous tree-construction by Goldreich-Goldwasser-Micali (GGM). Similar to lecture 7, the proof uses a hybrid argument, but this time, the hybrid argument is a bit more involved. The lecture video is split into three parts, the lecture notes are below.

      Links to the videos: Part 1, Part 2, Part 3
    • 09 Lecture Folder

      This lecture covers the Goldreich-Levin hardcore bit (and uses a Chernoff bound) showing that one-wayness implies pseudorandomness. The lecture consists of 2 parts, lecture notes are below.

      Link to lecture videos: Part 1, Part 2

    • 10 Lecture Folder

      This lecture by Pihla covers a separation for public-key encryption from one-way functions. It consists of 3 parts. Pihla's handwritten lecture notes are below.

      Link to lectures: Part 1, Part 2, Part 3

    • 11-lecture Folder

      This lecture covers, how, in general, to construct PRGs from OWFs. The lecture consists of 2 parts.

      Lecture videos: Part 1, Part 2

      Below is a draft version of the lecture notes. It does not have all the proofs, but I hope that it is still useful!

      **EDIT March 25, 2024:** Small update of the lecture notes.

    • 12-Lecture Folder

      This is a summary lecture of the Foundations Track of the course. Link to Lecture: Video

      There are no lecture notes accompanying this summary lecture.

      Update (March 30, 2024): 

      • Deadline for the quizzes is April 8, 10:00.
      • Instead of a walk as announced, I will bring tea for a round of tea on Monday, April 8, at 10:00 to our usual classroom.


◄ Previous section
Course Organization
Next section ►
Foundations Assignments