2
$\begingroup$

I need a bit of clarification about the definition of transcript of a simulator in Zero-Knowledge Proofs.

Basically, the way I understood it, the simulator is given access to the (potentially malicious) Verifier as a sub-routine, and the goal of the simulator is produce a transcript that's computationally indistinguishable from the transcript produced between the Prover and the (potentially malicious) Verifier.

My question is: Does the transcript of the simulator include the final Accept/Reject output of the verifier or not? In other words, if the verifier accepts in an interaction with the real Prover, should the simulator also be able to produce a transcript, that will be accepted by the verifier, or can the simulator just leave the verifier's output out.

If it leaves the verifier output, then the definition doesn't seem to make sense to me, because I can always generate a random transcript that looks like the interaction between prover and verifier. However, in most lectures, I don't see people requiring the result of verifier in the transcript, which is what's confusing me.

$\endgroup$
3
$\begingroup$

There are two formulations which are equivalent. One formulation is where the simulator outputs the verifiers view and the other where the simulator outputs the verifier's output. In neither case does the verifier's output need to be present. However, since it depends the verifier, and we quantify over all PPT verifiers, the simulation must work also where the verifier outputs accept/reject on top of whatever else it may want to output.

These formulations are equivalent since the distinguisher can just run the verifier on its view to get the output.

Just to complicate things, note that if a definition is used that allows an expected polynomial-time verifier and simulator, then the distinguisher cannot run the verifier on its view unless it too runs in expected polynomial-time (and things are typically not formalized this way). However, this really isn't very important and you should be able to ignore this complication.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.