3
$\begingroup$

I was reading the Zero knowledge property for Interactive Proofs. It said that for the proof to be zero knowledge, there should exist a simulator that runs in expected polynomial time for all verifiers, such that the simulator can generate a distribution which is identical to the view of the Verifier.
What was the need of formalizing this property with such a simulator?
Is it formalized with a simulator that runs in polynomial time, which has access to the random bits of Verifier, and which generates the Verifier's view only using the input to the proof and the verifier's random bits? This formulation seems much more intuitive to me.
Moreover, it also gives me a better idea as to why we allow the simulator to generate the random public string in NIZKP.
I am also confused as to how exactly the simulator is allowed to interact with the Verifier.

$\endgroup$
1
$\begingroup$

Simulator does not have access to random bits of Verifier. Expected polynomial time means expected value (expectation from probability theory) of running time is polynomial in problem size. Simulator is a kind of replacement of Prover, exchanging messages in exactly the same way.

Introducing your own definitions is ok, but you will be proving probably another statement (different protocol property) with your definition.

$\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.