Admission requirements
There are no formal admission requirements, but it is assumed that the student has some basic understanding of what an algorithm is, and brings along some familiarity with finite probability theory, as well as with modular arithmetic, group theory, finite fields, and polynomials. No (theoretical) computer science or complexity theory background is needed.
Description
This course provides an introduction to "interactive proofs", a fundamental concept and active research topic in theoretical computer science, particularly in complexity theory and cryptography. Interactive proofs offer remarkable properties: they can be used to prove (certain) statements that cannot be proven otherwise, to prove statements without giving away the proof itself, to prove statements so that it is sufficient to verify only a small portion of the proof, and more.
The first part of the course focuses on the complexity-theoretic aspects of interactive proofs. We will recall how computational problems are classified based on their difficulty, leading to the complexity classes P, NP, PSPACE, EXP etc., and we will study where the class IP, the class of problems that admit an interactive proof, fits within this hierarchy.
The second part of the course shifts to cryptographic aspects, where in particular we discuss zero-knowledge proofs. These are special types of interactive proofs that convince the verifier of the truth of the considered statement without revealing any additional information (in particular, preventing the verifier from reusing the proof to convince someone else). We will also discuss proofs-of-knowledge, which in addition to the truth of the statement also convince the verifier that the prover knows some related information (an NP witness). A particular challenge will be to formally define these cryptographic properties. Finally, we will show how some of these interactive proofs can be transformed into non-interactive ones by applying the Fiat-Shamir heuristic.
If time permits, we will also touch upon succinct proofs; these are interactive proofs that are significantly shorter than their non-interactive counterparts.
Course Objectives
By the end of this course, students are expected to: - develop a rigorous understanding of the formal definition of an interactive proof system and of the considered variants, - become familiar with several (historically) important and concrete examples of interactive proof systems, - gain a broad understanding of the theory of interactive proofs, including both classical and modern results (to the extent covered in the course), and - be able to analyze and evaluate typical interactive proof systems with respect to their properties.
Timetable
In MyTimetable, you can find all course and programme schedules, allowing you to create your personal timetable. Activities for which you have enrolled via MyStudyMap will automatically appear in your timetable.
Additionally, you can easily link MyTimetable to a calendar app on your phone, and schedule changes will be automatically updated in your calendar. You can also choose to receive email notifications about schedule changes. You can enable notifications in Settings after logging in.
Questions? Watch the video, read the instructions, or contact the ISSC helpdesk.
Note: Joint Degree students from Leiden/Delft need to combine information from both the Leiden and Delft MyTimetables to see a complete schedule. This video explains how to do it.
Mode of Instruction
Lectures and some take-home exercises.
Assessment method
The examination consists of homework and an oral (retake) exam. The homework counts as a practical. There is no retake for it and it is evaluated on the basis of pass/fail. A pass is required to take part in the exam. The homework does not count towards the final grade, which is based only on the oral exam.
Reading list
none
Registration
As a student, you are responsible for enrolling on time through MyStudyMap.
In this short video, you can see step-by-step how to enrol for courses in MyStudyMap.
Extensive information about the operation of MyStudyMap can be found here.
There are two enrolment periods per year:
Enrolment for the fall opens in July
Enrolment for the spring opens in December
See this page for more information about deadlines and enrolling for courses and exams.
Note:
It is mandatory to enrol for all activities of a course that you are going to follow.
Your enrolment is only complete when you submit your course planning in the ‘Ready for enrolment’ tab by clicking ‘Send’.
Not being enrolled for an exam/resit means that you are not allowed to participate in the exam/resit.
Contact
The lecturer can be reached via email: serge.fehr@cwi.nl
Remarks
Software
Starting from the 2024/2025 academic year, the Faculty of Science will use the software distribution platform Academic Software. Through this platform, you can access the software needed for specific courses in your studies. For some software, your laptop must meet certain system requirements, which will be specified with the software. It is important to install the software before the start of the course. More information about the laptop requirements can be found on the student website.