If you have participated in CS-E4340 Cryptography, you will have sufficient pre-requisits to follow this course. If you have not followed CS-E4340 Cryptography but are familiar with proofs (in general) and discrete probabilities, following this course should still be possible. Essentially, you need to read up on 3 definitions: One-way functions, pseudo-random generators and pseudorandom functions. If you haven't participated in CS-E4340 Cryptography, please contact one of the teachers as soon as possible so that we can provide you with good pointers to the material. One option is to watch Lecture 1-3 of CS-E4340 Cryptography, which cover these definitions. Alternatively, you can read the lecture notes and/or have a look at Foundations of Cryptography I by Oded Goldreich.
Teaching period III covers hardness amplification in cryptography, and teaching period IV covers key exchange and secure multi-party computation. In addition, individual (short) presentations will cover specific research topics such as quantum cryptography and cryptographic applications of secure multi-party computation. If you are only interested in one half (e.g., if you think the first half is too theoretical or the second half is too applied), you can replace one of the halves by giving a presentation on a research topic in cryptography (for details, see organization).
Teaching Period III: Hardness amplification in cryptography
From the introductory course in cryptography, we know that one-way functions (OWFs) imply pseudorandom generators (PRGs) and that PRGs imply pseudorandom functions (PRFs). Moreover, PRFs also imply OWFs, so all three primitives are equivalent. While we gave some intuition for why this is true, we also discussed that OWFs are a very very very weak notion of security. So, how can it be that we can build something as strong a cipher/PRF just from a OWF? Understanding how this exactly works is the goal of this teaching period as well as understanding limits of what we can prove. Below is a (preliminary) outline of the contents:
1) PRGs which map n bits to n+1 bits can be turned into PRGs which map n bits to p(n) bits for some arbitrary polynomial p.
2) Length-doubling PRGs can be turned into pseudorandom functions via the Goldreich-Goldwasser-Micali construction. (1) and (2) are interesting and useful also because they demonstrate a technique known as hybrid argument.
3) We know that bijective, length-preserving OWFs can be turned into PRGs via the Goldreich-Levin hardcore bit. We prove that the Goldreich-Levin construction is, indeed, a hardcore bit.
4) We prove that, in general, OWFs can be turned into PRGs. This was originally proved by Hastad, Impagliazzo, Levin and Luby, but we present a simpler proof (and more efficient construction) by Vadhan and Zhang. (3) and (4) are interest and useful also because they show us how to turn a distinguishing algorithm (which only gives us 1 bit) into a search algorithm (which gives us a string, namely a pre-image).
5) So far, we stayed within MiniCrypt, i.e., things that are equivalent to OWFs. But what if we wish to move beyond MiniCrypt? Can we build, e.g., public-key encryption from one-way functions? We do not know a definite answer, but the oracle separation by Impagliazzo and Rudich gives us some indication. We prove this oracle separation result.
6) ...this is about stronger cryptography, but what about weaker cryptography? Can we build one-way functions based on weaker assumptions? We will see a separation results that shows that it might be hard to build one-way functions merely from the assumption that NP is not equal to P. (5) and (6) are interesting also because they show how limitations of standard techniques.
7) Another nice topic of hardness amplification is trying to build a one-way function from weaker notions of one-wayness. If we have time for this, I hope, I will be able to show it.
Teaching Period IV: Key exchange and secure multi-party computation
How can we agree on a key via an insecure network? How do we construct a secure key agreement protocol? We cover:
1) The security definition(s) for secure key exchange.
2) Construction principles for a good key schedule, and construction principles of a good key exchange from a good key schedule.
3) Since real-life key exchange protocols such as TLS and MLS are terribly complicated, we use formal verification techniques to write proofs. We will discuss some of these techniques (and perhaps even try some out).
How can two or more mutually distrusting parties perform a computation together on data that they want to keep secret? We will cover main tools of secure multi-party computation:
1) Security definitions for secure multi-party computation, the simulation paradigm.2) Garbling schemes, especially Yao's garbling scheme.
3) Oblivious transfer
We look forward to forming a crypto course community, and we would like to have more "live" interaction than in the basic crypto course - since we are a (much) smaller group, this will hopefully also be easier (possibility to study on your own timing will be maintained - we know, some of you have a full-time professional life...). The idea is to have the "live" interactions every Monday between 10-14, including both, exercises and lectures. The plan is roughly like this: 45 min. exercises, 45 min. lecture, 1h lunch break, 45 min. lecture, 45 min. exercises. The timing within the slot might slightly change, but the main idea is that between 10-14, we all spend 3 hours together (but not necessarily in a Zoom call throughout the whole thing, but at least with Zoom calls in the beginning and in the end, and possibly some more... ...I will communicate details on a weekly basis).
Below, I describe how I imagine our interaction and which platforms will be used. If it's hard for you to imagine the interaction, consider giving it a shot - it's the same for us, it's still all quite new :-) And don't worry if you really don't like certain modes of interaction, that's okay, you can skip over sessions you don't like and just ask your questions in a different platform then. In any way you prefer to engage, we will welcome and support you. We are glad you chose to join :-)
- Live sessions take place over Zoom. We will start the first session of this course with some interactive session where people will be divided into random small groups of 3 people. There will be a different task for each small subgroup with a small 1-minute-presentation of the results by each group. In addition to the content of the task, the goal of this exercise is to reduce anonymity in the classroom. It might be daunting especially for those who feel shy, but I promise that it is worth to participate. We will try out to use break-out rooms also for the exercise sessions so everyone can discuss in small subgroups. You can opt-out of break-out rooms if you prefer to work on your own and only want to use the exercise session as office hour of the teachers.
- We will have a Zulip community. We sent invitation links to anyone who was registered on January 8, 2021. If you registered later, please send a message to Estuardo, Pihla, Kirthi or Chris to be added.
- Join the course's Zulip streams by clicking the invitation link under 'Materials'. If you have problems accessing the course's Zulip, please contact one of teaching assistants via eMail. Note that we do not use the MyCourses Forum in this course.
- The main lectures will be pre-recorded (else, we rely on technology robustness too much), but there might be some additional parts of the lecture which might be live. You can find a link to the lecture video in the materials section of the MyCourses page.
- Exercise Sheets are posted here on MyCourses in Assignments. You can return your solutions also here on MyCourses, and we will post the feedback here on MyCourses. Return deadline for the solutions to the exercise sheets is every Wednesday at 14:00. First deadline is Wednesday, January 20, at 14:00. Submitting late is always possible. Feedback will be given also on late submissions, points are only given on submissions handed in before the deadline.
- The course is pass/fail, no grades (no exception possible), no exam. Passing criteria are sufficiently many participation points, namely at least 25 points overall. There are 10 exercise sheets, each of which yields at most 4 points. Additionally, you can volunteer for giving peer feedback, i.e., you will give feedback to one or two of the other course participants. The goal of this is to engage with each others thoughts and engage in reading and writing at the same time. You do not need to give points for the peers, this will be done by the teaching assistants. Giving peer feedback yields up to 2 points per 4 exercises. Finally, this course is intended to bring you to the research boundary in cryptography - so, if you have some specific interest, you can volunteer to give a presentation (15-20 minutes). The presentations shall be pre-recorded and drafts shall be submitted ahead of time. If you are interested in giving a presentation, please contact Chris latest on January 26. A presentation yields up to 10 participation points (and essentially can replace participation in one half of the course --- e.g., if the first half is too theoretical or the second half is too applied, you can choose this path.).