1
$\begingroup$

In the literature, when reading about zero knowledge proofs, the prover (prover/verifier) is always given an unlimited computational power or just capacity to solve NP.

Is it necessary for the prover to have higher computational power than the verifier?

If it is, is there any variant that does not need this property?

If any of the answers is yes can you give me references?

$\endgroup$

1 Answer 1

1
$\begingroup$

If the prover has the same power as the verifier, then the verifier can simulate the entire interaction himself, which makes the interactive proof unnecessary. For example, if we have an interactive proof with a probabilistic polynomial verifier and a polynomial prover for some language $L$, then $L\in BPP$. When dealing with interactive proof systems with a polynomial verifier it suffices to consider PSPACE provers, since a PSPACE prover can find and send the messages that maximize the verifier's acceptance probability.

Note that the above refers to interactive proof systems in general, there's nothing specific to zero knowledge (zero knowledge simply adds the condition that for yes instances, the entire communication of the protocol can be generated by a simulator who only has access to the input).

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