Materials
These are the lecture notes for the first lecture. They also contain relevant administrative information.
These are updated lecture notes of the second lecture where I corrected some typos.
Second update (Sept 21, 2018): negligible functions map to the real positive numbers.
Third update (Sept 22, 2018): I corrected the same error at several additional occurrences of negligible functions.
Update Oct 14, 2018: I added the set analysis for the reduction.
Update Oct 15, 2018: I corrected a few typos and added some additional explanations.
Sept 21: 2018: This is a draft of the first 45 minutes of the 3rd lecture next Monday (Sept. 24, 2018). I will add the rest of the lecture notes on Monday.
Update on Sept 23, 2018: This is a draft of most of the lecture notes. One of the reduction proofs in the end of the lecture is still missing.
Update on Sept 24, 2018: These are the complete lecture notes for the lecture.
Update on Oct 14, 2018: Added a missing reference to a paper by Boaz Barak. Fixed formatting issues of the Claim in Section 4.1
Oct 1: This is a very coarse draft of the lecture notes that mostly contains the relevant definitions for reference. We will update the lecture notes versus the end of this week to include the theorems and proofs discussed in this lecture.
Oct 7 (Update): The lecture notes now also contain the theorem and the proof that was discussed in the lecture.
Oct 7: This version of the lecture notes covers the first half of the lecture. Will be updated soon to also contain the second half.
Oct 8: Update on the lecture notes. Tonight, I will either add the remaining proofs or handwritten notes of the remaining proofs.
Oct 8: These are the complete lecture notes of lecture 5 now.
Oct 14: The previous version of the lecture notes of lecture 5 claimed that exercise 20 shows that xor of all bits is not necessarily a hardcore bit. Indeed, the statement is true, but exercise 20 does not provide arguments for that. We thus added a short discussion of the arguments for this claim to the lecture notes.
In this lecture, we introduce pseudorandom functions which are, essentially, stream ciphers and will be tremendously useful for building symmetric encryption schemes, message authentication codes and other cryptographic primitives in the second half of this course. In the lecture, we will see that one can build pseudorandom function from pseudorandom generators.
Oct 15: Some proofs are still missing.
Oct 15: Proofs are included into the lecture notes now.
Oct 15: Added intuition for the GGM construction and the GGM proof as well as the formal definition of a pseudorandom permutation.
The topic of this lecture are message authentication codes. These lecture notes also contain information about an alternative path for the second half of the course. Note that registration deadline for the alternative path of the course is Wednesday, October 31, 2018.
Oct 29: Update on the lecture notes, "=1" in correctness criterion was missing before.
Oct 31: Update on the lecture notes, corrected a few typos, improved clarity of pseudo-code
This is part of the proof of the claim that the MAC tag leaking message authentication scheme m' is UNF-CMA-secure.
Nov 5: Update, correction of various typos
These slides contain the essential technical arguments to show that PRFs imply MACs. We will add lecture notes for lecture 8 in addition to the slides to provide some more detailed explanation on the proof structure.
Nov 5: Update, correction of various typos
High-level structure of the proof that PRFs imply MACs. Please also consult the slide set 08-Lecture-PRF-to-MAC.
November 8: Fixed small type in the oracle description in Definition 2.1
Lecture Notes on symmetric encryption, asymmetric encryption and the Bleichenbacher attack
Details on the Bleichenbacher attack