CRYPTO NEWS

The significance of rewinding a simulation in an ZK interactive proof

I’m reading Matthew Green’s blog post on ZK Interactive Proofs

I don’t understand the part where he explains how using a time machine shows that the prover is leaking zero information

Specifically, assume that I (the Verifier) have some strategy that
‘extracts’ useful information about Google’s coloring after observing
an execution of the honest protocol. Then my strategy should work
equally well in the case where I’m being fooled with a time machine.
The protocol runs are, from my perspective, statistically identical. I
physically cannot tell the difference.

Thus if the amount of information I can extract is identical in the
‘real experiment’ and the ‘time machine experiment’, yet the amount of
information Google puts into the ‘time machine’ experiment is exactly
zero — then this implies that even in the real world the protocol must
not leak any useful information.

I am not sure I am convinced about this. I assume that the transcript of the simulation doesn’t contain the repeated/uncorrected iterations of each try. i.e. I think it will contain only the final correct simulation of each try i.e. if verifier chooses 2 vertices which are coloured different, then that step will be in the transcript. However, if the verifier chooses 2 vertices with the same colour, then the prover will operate a time machine & maker the prover forget about that try & redo it. I assume in this case, the transcript will only contain the redone try & not the try which failed. Am I right about this?

Assuming my assumption about the transcript is true, then the transcript contains only all the verified tries & all the tries where verifier had to use the time machines to reverse wouldn’t be recorded in the transcript. And the verifier cannot extract any info from such a transcript.

So in the end, he writes

And yet it’s worth pointing out again that in the time machine version, Google has absolutely no information about how to color the graph.

But this is not true in the real world, right? There is no time machine in the real world. So the prover cannot convince the verifier without having actual knowledge. So how exactly does a transcript which was "corrected" using a time machine to convince the verifier prove that an actual transcript doesn’t leak info?

The significance of rewinding a simulation in an ZK interactive proof

Shopping cart
There are no products in the cart!
Continue shopping
0