Seminar on Zero Knowledge Proofs
Id: 0368-4152-01

Iftach Haitner

Tuesdays: 10:00-12:00, Room: Shenkar 105

Zero-knowledge interactive proofs are fascinating constructs which enable one party (the "prover") to convince another party (the "verifier") of an assertion (.e.g., a mathematical theorem) , with the property that the verifier learns nothing other than the fact that the assertion being proven is true. In addition to being powerful tools for constructing secure cryptographic protocols, zero-knowledge proofs yield rich classes of computational problems that are of both complexity-theoretic and cryptographic interest

The the seminar we will follow the survey by Salil Vadhan, and then )move to more recent results

In each meeting one student will cover a single topic as listed below.

Undergrad studetns

Third year students who are willing to work hard, are welcome to join the seminar, but please consult me via email before registering.


This is an advanced seminar, so background in the theory of computation (Algorithm, Computability, Complexity) is required. Students with particularly strong math background are also welcome.


Power Point presentations are acceptable, but white boards ones are preferable.
To do a good job one needs to read background material, see the reading section.
In addition, the speakers of the week will have to give me a practice talk a week before (right after the talk of that week).

Topics and schedule

# When Who What
1 01/3 Udi Peled Introduction
Section 1
2 08/3 Nathanel Ozeri Definitions
Section 2
3 15/3 Noam Mazor Statistical Difference part
Section 3.1
4 22/3 David Agassi Statistical Difference part
Section 3.2
5 29/3 Omer Anson Analysing General HSVSZK proofs
Section 3.3
6 05/4 Alon Elmaliah
& Barak Sternberg
Entropy Difference to Statistical Difference
Section 3.4
7 12/04 Zahi Taub
& Dafna Sade
Applications of Complete Problems part
Sections 4.1--4.4
8 03/5 Barak Arkis Applications of Complete Problems part
Sections 4.5--4.8
9 10/5 Elazar Gershoni
& Michael Shkolnik
Private Coins Vs. Public Coin
Section 5
10 17/5 Gal Rotem Coping with Cheating Verifiers
Section 6
24/5 No Class
11 31/5 Alon Brutzkus Noninteractive SZK
Section 7
12 07/6 Udi Peled An Unconditional Study of Computational Zero Knowledge
Paper by Salil Vadhan