Credits: 5

Schedule: 07.01.2020 - 30.03.2020

Contact information for the course (applies in this implementation): 

Teaching Period (valid 01.08.2018-31.07.2020): 

III-IV Spring (2018-2019, 2019-2020)

Learning Outcomes (valid 01.08.2018-31.07.2020): 

Having completed this course, you will be familiar with an area in the foundations of cryptography on a level of familiarity that is required for engaging in research in that area. You will be able to use techniques from algorithm analysis, complexity theory and/or discrete mathematics to study the hardness of a class of average-case problems. The content of the course varies and so do the learning outcomes. In particular, the classes of average-case hard problems vary from semester to semester.

Content (valid 01.08.2018-31.07.2020): 

The content varies each year and lies within the field of using discrete mathematics techniques for algorithm analysis. The Spring 2019 instance will cover algorithms for random constraint satisfaction problems as well as as algorithms for inverting Goldreich's one-way function. We will study solution spaces of the problems and see how those relate to algorithmic difficulty.

Details on the course content (applies in this implementation): 

We cover two different areas of cryptography in teaching period III and teaching period IV, as described below. The main path through this course is via lectures and exercises. There will be 5 exercise sheets per period, with 4 points each. You need 25 points to pass the course, and in each of the two periods, you need at least 10 points.

Alternative path through the course: If you are only interested in one of the two areas, you can contact Chris before January 15. We plan to offer alternative reading groups for those who prefer to study only one of the two areas. I.e., we will choose, read and discuss interesting papers together. You can make suggestions for papers that you would be particularly interested in reading.

Independent Assignments: If you would like to, you can also take part in the both pathes. In that case, the reading group will be treated as an independent assignment. If you are interested, contact Chris before January 15.

Topics of the main path:

Teaching Period III:

We cover computational hardness as a foundation of cryptography. What is the connection between NP-hardness and one-way functions? If I have one-way functions, what can I build? If there are no one-way functions, can I still have very useful cryptography? (The answer is no.) What are zero-knowledge proofs?

Teaching Period IV:

We will study the security of the TLS 1.3 Handshake protocol and how to prove its security.

Assessment Methods and Criteria (valid 01.08.2018-31.07.2020): 

Weekly exercises, course feedback (no exam)

Elaboration of the evaluation criteria and methods, and acquainting students with the evaluation (applies in this implementation): 

Note that the course is not graded, i.e., it is only graded with pass/fail. There will be 10 homework assignments, each of which yields up to 4 points. One passes the course with 25/40 points. The main point of the course is to provide an opportunity to acquire research-level knowledge in cryptography, and the exercises are aimed at providing a safe space for exploring one's thoughts and obtaining feedback that helps to improve one's thinking. That is, optimally, the TA will have the opportunity to give feedback on mistakes that were made. Thus, 1 point per exercise is given for a genuine attempt at solving it. 2 points are given for a mostly correct solution. We aim to provide sufficiently many exercises such that one can obtain enough points by making exclusively genuine attempts (since they are most likely to yield best learning gains), so that the grading does not interfere with the learning. I.e., in this course, it is not necessary to "game the system" to "gain points".

We recommend weekly participation in the exercise sessions since asking questions to the TA is crucial. We also recommend weekly handing in of exercises. Note that handing in exercises also gives weekly feedback to the lecturer. In that sense, it is particularly useful feedback for the lecturer if you hand in exercise solutions in a week when you found the lecture difficult to understand.

Workload (valid 01.08.2018-31.07.2020): 

Lectures 24h (12 2h-sessions), Teaching in small groups 24h (12 2h-sessions), weekly written exercises 36h, self-study ca. 40h

Study Material (valid 01.08.2018-31.07.2020): 

Varies depending on the course content and will be announced later.

Details on the course materials (applies in this implementation): Week 1-6: Foundations of Cryptography I, Oded Goldreich (available in the library and also as online draft on Goldreich's website)
Week 7-12: TLS 1.3 Standard and the ePrint article containing the proof we discuss

Course Homepage (valid 01.08.2018-31.07.2020):

Prerequisites (valid 01.08.2018-31.07.2020): 

Essential prerequisite skills are mathematical maturity and discrete probability theory. Highly recommended is a background in computability and complexity, especially basic complexity classes such as P and NP. It is further helpful to have a background in cryptography and/or algorithms.

Grading Scale (valid 01.08.2018-31.07.2020): 


Additional information for the course (applies in this implementation): 

If you have participated in "Cryptography and Data Security", then you will be able to follow the course. In the beginning, we will review the necessary complexity-theory background for those who might not have had the opportunity to study these great concepts in their undergraduate degree.

Details on the schedule (applies in this implementation): 

Tentative Schedule:

Week 1: One-Way Functions, counterexamples to one-way functions, negligible functions

Week 2: Reductions, Pseudo-Random Generators (PRGs), Pseudorandom Functions (PRFs)

Week 3: Pseudo-Random Generator Stretch Expansion (Hybrid Arguments)

Week 4: PRGs => PRFs Goldreich-Goldwasser-Micali Construction (Hybrid Arguments)

Week 5: Goldreich-Levin Hardcore Bit (OWFs => PRGs)

Week 6: Zero-Knowledge

--- Break ---

Week 7: Diffie-Hellman, TLS 1.3 Key Agreement and TLS 1.3 Key Schedule

Week 8: Security Properties and Security Definitions of the TLS 1.3 Key Schedule

Week 9: Cryptographic Primitives: Collision-resistence, Key Derivation Functions, Diffie-Hellman

Week 10: Proof overview

Week 11: Proof of Collision Resistance

Week 12: Proof of Key Indistinguishability


Registration and further information