# ZK course
## Week 1
### Lecture
1. Cage example
2. Intuition of what is zk
3. definition of IP and LIN, QR, and SAT example
4. QNR
5. Relation among IP and other complexity classes
6. GNI in IP, but not known to be in NP
8. IP=PSPACE
9. public coin vs private coin (how to simulate it)
### Tutorial
1. Characterize languages that can be proved probabilistically yet non-interactively. (BPP)
3. Schwartz-Zippel lemma
4. A simple fact from number theory: $p \in \mathbb{P}$ iff $(X+1)^p = X^p + 1$ in $\mathbb{Z}_p[X]$ (voluntary homework: prove it!). Can we use Schwartz-Zippel directly here to check whether $p \in \mathbb{P}$?
5. PSPACE $\subset$ IP using #SAT
6. Matrix multiplication IP
7. Color-blindness
## Week 2
### Lecture
1. zero knowledge definitions (ZK and idea of simulatiotn, perfect, statistical and computational flavour)
2. hybrid argument
3. commitment scheme
4. Hamiltonoicity and ZK proof system for Hamiltonicity
### Tutorial
1. Finish the sumcheck proof
2. No statistically hiding + binding commitments (explain why this implies we can only get CZK for HAM because we need stat soundness, mention comp soundness)
3. How to use a hash function for a commitment scheme (H(m) is not binding because of H being a random fn)
## Week 3
### Lecture
1. what knowledge means and definition
2. some examples
3. ZKPoK for all NP via Hamiltonicity
### Tutorial
1. Mention that pure hash is not hiding either
2. Show that DIP = NP.
4. If there exists a prover that succeeds at cheating, then we can reduce it to breaking the binding of the commitment (\exists A* st. breaks any commitment)
7. ZK proof that your commitment is valid (define the language, {(m,c) \| \exists is the full language})
5. 3-colorability ZKP.
9. https://web.mit.edu/~ezyang/Public/graph/svg.html
## Week 4
### Lecture
1. what knowledge means and definition
2. some examples
3. ZKPoK for all NP via Hamiltonicity
### Tutorial
1. Alternative for HAM
3. GI ZKP
## Week 5
### Lecture
1. Definiton of sigma protocol
2. Schnorr protocol
3.
### Tutorial
1. GI: Show that this is a PoK with k.e. $\frac{1}{2}$
2. 3COL: Show that this is a PoK with k.e. $1 - \frac{1}{\mid E \mid}$
4. KE for HPIP which always outputs => KE for P* with k.e. = s.e.
5. 
6.
9. Pedersen commitment (comp. binding, perfect hiding)

## Week 6
### Lecture
1. OR and AND compositions of sigma protocols
2. DH tuples protocol
3. examples

### Tutorial
1. 
3. Shamir secret sharing
4. k-out-of-n alternative for sigma-protocols [source](https://www.win.tue.nl/~berry/papers/crypto94.pdf)

## Week 7
### Lecture
1. Constant round CZK
2. Starting parallel repetition impossibility

### Tutorial
1. Finish 
2. Prove that you know the committed value using Pedersen
3. Finish the details: k-out-of-n alternative for sigma-protocols
4. NIZK without CRS implies BPP (unidirectional ZK is trivial)

## Week 8
### Lecture
1. Finishing parallel repetition impossibility
2. 3 round impossibility
3. constant round AM impossibility for BB ZK

### Tutorial
1.
1. Finish the proof for $y = w^q$, $q$ small by setting $q' = q + \alpha \phi(n)$ for some $\alpha$ s.t. $q' \in \mathbb{P}$ (Dirichlet thm on primes in arithmetic progressions).
2. Note: this doesn't work for $q = 2$, where the protocol reduces to the QR protocol.
3. Note that sigma-protocols are invariant under parallel repetition (HVZK is preserved), so I think it's the best thing we can do
3. Show that Fiat-Shamir isn't sound for a constant-soundness sequential repetition
4. Prove that Fiat-Shamir is sound in constant round, negligible soundness in ROM.

## Week 9
### Lecture x2 (no tutorial)
WI -> constant round ZK from WI
NBBZK -> Barak protocol

No tutorial
## Week 10
### Lecture
NIZK from CRS
### Tutorial
1. Fiat-Shamir continued.
1. Finish the proof of soundness in PROM.
2. Show ZK in PROM.
3. Notice it's no longer a proof, just an argument.
2. How to use ZK for passive => active security in MPC. $\{ (x, w) \mid x = (\textrm{out}, \textrm{public input}), w = \textrm{private input}, C(w, public input) = 1 \}$
3. Fiat-Shamir + Schnorr => Schnorr signatures (w = sk, hash m in FS)
4.
1. OR of Schnorr as ring signatures.
2. Application to cryptocurrency.
3. Note that ring signatures are non-trivial to construct.

## Week 11
### Lecture
MPC
### Tutorial
1. Fix the Pedersen commitment sigma-protocol extractor
2. Adaptive attack for Schnorr under weak FS (I can cook up $X$ which is a valid NIZK even though I don't know $x$ s.t. $g^x = X$, cf. [link](https://www.espe.edu.ec/wp-content/uploads/2023/10/crypto_attacks_ascrypto23_11zon.pdf)).
3. BB simulation => aux-input zk (sketch)
4. FS PoK by rewinding
5. Designated verifier ZK (via or statement)
6. MPC protocol as ZK (P has (x, w), V has x'. The variant P has only w is not ZK)

Simple MPC exercises, OT, impossibility results for honest majority
## Week 12
Plonk. Starts at 9.15am

7. IOP + crypto compiler for 3COL.
8. Polynomial commitments (KZG)
## Week 13
### Lecture
MPC-in the head
### Tutorial
- malleability of Pedersen commitment
- e-voting introduction
- NIZK proof for $x_1 + \dots + x_n = 1$ through malleability
## Week 14
###
Non-Malleability
### Tutorial
- joint DL NIZKPoK for election
- show how to update the pp in KZG PCS
- sudoku
- Groth-Sahai
- questions?
## Week 15
Student presentations

### Tutorial someday
3. PoK => soundness
8. https://kodu.ut.ee/~swen/courses/crypto-ii/10-exercises.pdf
9.
10. 2-round aux-input ZK is trivial./

Questions for the exam:
Basic questions that you should know to pass the exam (3):
1. talk about some base ZK protocol: hamiltonicity / 3-colorability / Graph Isomorphism. For each of them it is important to remember if they are for all NP or not, the soundness error and how to decrease it
2. sigma protocols, definition and some scheme like Schnorr (either show the protocol or prove that the protocol is a sigma protocol)
3. NIZK, i.e., how to obtain a NIZK starting from an interactive protocol. We have seen two techniques during the course: ROM or CRS
4. bonus question: how to make a semi-honest secure protocol a malicious secure protocol

Questions to ave a good mark (4):
1. give the difference between strong and weak FS
2. CZK versus SZK noticing the difference in obtaining it on a protocol for all NP (like the one for hamiltonicity). It is important also to explain the soundness security that it is possible to achieve in the two cases
3. what happens if we repeat multiple time a zk protocol, considering the case of parllel and sequential repetitions, in case of ZK or HVZK

More enanced questions (4.5):
1. MPC inthe head intuition
2. OR composition of sigma protocols
3. How to achieve constant round ZK

Pros questions (5/5!)
1. techniques used for Plonk
2. impossibility results on ZK with lower bounds
3. Barack's protocol