1
$\begingroup$

I have read Arora, and Sipser chapters discussing IP, but have not seen mention of such a possibility. Given that a Prover is computationally unbounded is it not possible under certain circumstance that the Prover could just build all possible Verifiers for the Language at hand and simulate one that closely (or perfectly) mimics the one it is interacting with?

Perhaps I'm being ignorant, but it seems to me an aspect of Interactive Proof Systems that is assumed but poorly specified is that the Prover must know something (maybe even everything) about the language we are trying to verify, or else the Prover wouldn't be very good at being convincing. Put another way: It seems the Prover knows what the problem being verified is, and this aspect of the Prover doesn't seem well specified.

If the Prover knows what the problem/language at hand is then is it not possible that even in the private coin model given certain properties of the problem the Prover could just figure out all reasonable verifiers for the problem and simulate them?

$\endgroup$
3
  • $\begingroup$ You'd need to say more specifically how you think it would help the prover to simulate the verifier, I think. For example, for NP, consider a verifier for 3-SAT. If the given formula is not satisfiable, there is no way to somehow fool the verifier (who expects to be given a satisfying assignment, and simply verifies that the given assignment satisfies the formula) into incorrectly saying that the formula is satisfiable. In more complicated classes (e.g. probabilistically checkable proofs) the verifier can, say, access random bits. The prover can't, so can't know the verifier's state. $\endgroup$
    – Neal Young
    Dec 16, 2022 at 21:55
  • $\begingroup$ I agree, given only knowledge about the input and message history the prover can not know the state of the verifier. But assuming that the Prover knows the Language the verifier is trying to verify is it not possible that the prover can leverage that knowledge? For instance, maybe certain Languages can only have a finite amount of reasonable verifiers, then the Prover could in theory enumerate all possible verifiers (including all possible coin flips) and just pick the best one, without knowing anything beyond the inputs, and message history. $\endgroup$
    – Ben Jenney
    Dec 16, 2022 at 22:04
  • 1
    $\begingroup$ Generally the prover does know the language that the verifier and prover are working with, indeed, the prover and verifier are defined specifically for a given language. And the prover generally is assumed to know the verifier's algorithm. This is not a problem. Note that the coin flips are done anew for each execution of the prover/verifier interaction, so the prover does not know the coin flips (except to the extent that they are conditioned by the verifier's responses). Maybe consider some specific examples, to understand this all better. $\endgroup$
    – Neal Young
    Dec 17, 2022 at 3:10

1 Answer 1

0
$\begingroup$

The prover can indeed simulate a verifier: indeed, the prover can simulate all verifiers which perform their task properly, and do so for each possible collection of coin flips. So if there are a million possible verifiers and 100 coins, the prover can just simulate all $1000000\cdot2^{100}$ possibilities for each of the possible proofs it would generate. Indeed, you could even use this as an algorithm for finding a proof for the verifier: generate all proofs of length 1, 2, ... until you find one that works for all possible verifiers and coin states. But for interactive proof systems, we usually just care about whether there is such a proof, or whether even an all-powerful system would not be able to find one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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