MS-E1687 - Advanced Topics in Cryptography V D, Lecture, 8.1.2024-8.4.2024

Osion kuvaus

• Foundations Materials
  • Valitse aktiviteetti 01 Lecture

    

    01 Lecture Kansio

    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.
    

  • Valitse aktiviteetti 02 Lecture

    

    02 Lecture Kansio

    • 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.

  • Valitse aktiviteetti 03 Lecture

    

    03 Lecture Kansio

    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

  • Valitse aktiviteetti 04 Lecture

    

    04 Lecture Kansio

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

    Videos: Part 1, Part 2

    Below are some notes.

  • Valitse aktiviteetti 05 Lecture

    

    05 Lecture Kansio

    •  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.

  • Valitse aktiviteetti 06 Lecture

    

    06 Lecture Kansio

    • "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.

  • Valitse aktiviteetti 07 Lecture

    

    07 Lecture Kansio

    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.
    

  • Valitse aktiviteetti 08 Lecture

    

    08 Lecture Kansio

    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
    
  • Valitse aktiviteetti 09 Lecture

    

    09 Lecture Kansio

    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

  • Valitse aktiviteetti 10 Lecture

    

    10 Lecture Kansio

    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

  • Valitse aktiviteetti 11-lecture

    

    11-lecture Kansio

    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.

  • Valitse aktiviteetti 12-Lecture

    

    12-Lecture Kansio

    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.