# zkLearning - Course notes

https://zk-learning.org/

## 01/17 Introduction and History of ZKP

[Lecture](https://www.youtube.com/watch?v=uchjTIlPzFo)

Classical proofs: axioms -> derivations from axioms -> declare a theorem is true

Proofs: a prover & a verifier (algorithms)
* Prover P:
* |*w*| = polynomial in |*x*|
* Claim string *x* (binary string)
* Message w (binary string)
* Length of *w* (|*w*|) is polynomial in the length of *x*

> This means that there exists some polynomial function *p* such that $$|w| \le p(|x|)$$
For example, if $$∣x∣=n$$ (let's say *n* is the number of bits in x), then a polynomial relationship might be $$∣w∣=n^2.$$ This means that as *x* grows, *w* will grow as the square of the length of *x*. Other polynomial relationships could be $$n, n^3, 4n^2+3n+10, etc.$$ The key is that the growth of *w* is bounded by some polynomial function of the size of x, rather than, say, an exponential function (which would be much faster growth).
> In the context of zero-knowledge proofs, the efficiency of the proof system (in terms of time and space complexity) often matters a lot. If the length of the witness (the secret information being used to prove a statement without revealing itself) grows polynomially with the length of the statement, it means the system can potentially be practical for larger inputs, as opposed to a system where the witness size grows exponentially (which would quickly become impractical).

Example: Claim: N is a product of 2 large primes
* If N=pq, V accepts; else V rejects
* proof={p,q}
* V knows: N is product of 2 primes, the two primes p and q -> Verifier knows extra information

Example: Claim: u is a quadratic residue mod N
* If y=x^2 mod N, V accepts; else V rejects
* Proof = X
* After interaction, V knows: y is a quadratic residue mod, square root of y (hard problem equivalent to factoring N)

Example: Claim: the two graphs are isomorphic
$$\pi: [N] \to [N], isomorphic$$
* If vertices on the left equal vertices on the right, V accepts, else rejects
* After interaction, V knows:
1) $$G_0 \ is \ isomorphic \ to \ G_1$$
2) $$the \ isomorphism \ \pi$$

Efficiently Verifiable Proofs (NP-Languages)
* Def: $$L$$ is an NP-language (or NP-decision problem), if there is a poly(|x|) time verifier V where
* Completeness [true claims have short proofs / honest provers]; check definitions

* Soundness [false theorems have no proofs / dishonest provers]; check definitions

Zero knowledge proofs' main idea: "Prove that I *could* prove it if I felt like it"

Zero knowledge interactive proofs:
* Two new ingredients: interaction & randomness
* Interaction: rather than passively "reading" proof, verifier engages in a non-trivial interaction with the prover
* Randomness: verifier is randomized (tosses coins as a primitive operation), and can err in accept/reject with small probability
* -> Lots of possible interactions

Example claim: This page contains 2 colors (how to prove colors are different to a blind verifier?)

Example claim: Interactive Proof for EQ

https://youtu.be/uchjTIlPzFo?t=1390

[[Goldwasser-Micali-Rackoff’89] Knowledge Complexity of Interactive Proof Systems](https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf)
* XXX

[[Goldreich-Micali-Wigderson’86] How to prove all NP-statements in zero-knowledge, and a methodology of cryptographic protocol design](https://link.springer.com/chapter/10.1007/3-540-47721-7_11)
* s

[[Fiat-Shamir’86] How To Prove Yourself: Practical Solutions to Identification and Signature Problems](https://link.springer.com/chapter/10.1007/3-540-47721-7_12)
* XXX

[[Bellare-Goldreich’92] On Defining Proofs of Knowledge](https://www.wisdom.weizmann.ac.il/~oded/PSX/pok.pdf)
* XXX

[Introduction to Zero Knowledge - Alon Rosen](https://www.youtube.com/watch?v=6uGimDYZPMw)
* XX

[Proofs of Knowledge - Yehuda lindell](https://www.youtube.com/watch?v=RvGsjnoYRRg)
* XX

[Demonstration of Zero-Knowledge Proof for Sudoku Using Standard Playing Cards](https://www.wisdom.weizmann.ac.il/~naor/PAPERS/SUDOKU_DEMO/)
* XX

[Boaz Barak - Zero Knowledge](https://files.boazbarak.org/crypto/lec_14_zero_knowledge.pdf)
* XX