History of ZKP

Let’s start with classical proofs. So when we think of a classical proof, we think about these various esteemed provers, Gauss, Euclid, Emmy Noether, Alan Turing, and our own, Steve Cook. And we think about theorems, the kind of theorems that you learn perhaps in geometry in class where there’s a bunch of axioms, there’s a claim that you’re trying to prove or theorem,you make a sequence of derivations from the axioms and then eventually you declare the theorem as proved. It could be the prime number theorem, the Pythagorean theorem, and so forth. But today, we’re going to think of proofas an interactive process where there is the prover. But maybe more importantly for our study, there is a verifier. So there is an explicit referenceto whoever it is that’s reading the proof and verifying it is correct. And we think about this as follows. There’s a claim, which is an input to both prover and the verifier. Both of the prover and the verifier are actually algorithms. And the prover sends a string, which we will refer to in this slide as a proof. The verifier reads this. So if you would like to think about that geometric proof, verifier is the teacher reading your proof and at the end accepting is it correct or reject. Accepting the claim as being proved or not. In fact in computer science, we often talk about efficiently verifiable proofs or NP proofs. And those are proofs where the string that the prover sends to the verifier is short. And the verifier, in addition, doesn’t have all the time in the world to read it, he has polynomial time. Now to be more explicit, what does it mean by short? What do we mean by polynomial? What we mean is that the string that the prover sends to the verifier is of size polynomial in the length of the claim. So we think about the claim as string x, binary string. The message here is string, binary string w, the length of w is polynomial in the length of x.

Claim: N is a product of 2 large primes

proof = {p, q}
If N = pq, V accepts
Else V rejects

After interaction, V knows:

1. N is product of 2 primes
2. The two primes p and q

Claim: y is a quadratic residue mod N
i.e
∃ x ∈ Z n ∗ s . t . y = x 2 m o d N \exist x \in Z^*_n s.t. y = x^2 mod N ∃x∈Zn∗​s.t.y=x2modN

Proof = x
If y = x^2 mod N, V accepts
Else V rejects

After interaction, V knows:

1. y is a quadratic residue mod
2. Square root of y(hard problem equivalent to factoring N)