ZKP MOOC Lecture 1: Introduction and History of ZKP

Shafi Goldwasser, ZKP MOOC Spring '23

[nicolasdecouttere]

Thanks Prof. Goldwasser. The use of practical, visual examples and historical references to research progress in the field add a lot of value.

[mukeshtiwari]

I believe there is typo on slide 19. The verification equation z^2 = sy^b (mod N) so if b = 1 then send z = r * sqrt (y) else send z = r (In the slides, it is other way round).

[DaltonSweeney]

Great lecture. It finally clicked for me after coming up with this general description of the interaction protocols:

The verifier asks the prover to perform task A or task B, but ahead of time the prover doesn't know which. If the prover _actually_ knows the secret, then it can always perform task A and B. But if the prover doesn't know the secret, then it can only "fake" one of the tasks. I.e. it can fake the correct answer for task A, but this means it doesn't have the answer for B (and vice versa). Assuming the verifier selects A or B at random, then a prover without the secret has a 50% chance of "faking" the wrong task, and therefore being unable to answer the verifier.

After 1 iteration there's a 50% chance the prover knew the secret and a 50% chance the prover faked it. After n iterations, there's a 1 - 1/2^n chance the prover knew the secret and a 1/2^n chance the prover faked it. The larger the n, the more convinced the verifier will be.

[portport]

gm. Always cool to hear ZKP explained by one of the inventors of ZKP

[xinyuzhang]

On slide 58 (G3-Colorable) ZKIP protocol, why does verifier reject if the two adjacent vertices have different colors?

[anusha]

If the verifier can query the prover multiple times for each possibility of b and use all the responses together to determine the secret, how is it still zero knowledge?
In the QR example, V gains two answers for both b=0 and b=1, and used them to deduce r. Before interaction he couldn’t have done this computation.

By definition of zk, the computation after interaction cannot be same as the computation before interaction in this case.

I feel that I’m missing something important in my zk understanding.