2
$\begingroup$

I'm having a difficult time understanding a concept from interactive proofs:

A trivial interactive proof for the graph isomorphism problem is having the prover just send a permutation that shows an isomorphism between $G_1$ and $G_2$, and have the verifier check it.

But what happens when $G_1$ and $G_2$ aren't isomorphic? If the prover really does know a solution to the problem, he'll just say that they aren't and we'll move on. But what if he always says that they aren't isomorphic? We have no way of knowing whether they really aren't, or whether the prover is lying, right?

So the prover might just always answer "not isomorphic" for any problem given to him, and we'll have no way of knowing whether he's correct or not.

So when we discuss interactive proofs (and Zero-Knowledge Proofs especially) do we always assume that the prover is capable of solving the problem?

Thanks

Improve this question
$\endgroup$
2
  • $\begingroup$ It is unclear what exactly you mean by "solve the problem", by the way, so my answer may be a bit off. $\endgroup$
    – fkraiem
    Jan 28, 2016 at 3:49
  • $\begingroup$ Mixing two cases (bounded vs lying prover) creates some confusion. $\endgroup$
    – Vadym Fedyukovych
    Jan 28, 2016 at 14:56

3 Answers 3

Reset to default
1
$\begingroup$

No, but if the problem isn't known to be in promiseMA then
we do "assume that the prover can always solve the problem".

https://cstheory.stackexchange.com/questions/696/mip-with-efficient-provers


Graph isomorphism is trivially in NP, so for graph isomorphism, we just
"assume that the prover" has an isomorphism between the graphs.
Graph non-isomorphism is not even known to be in MA, so for graph non-isomorphism,
we do "assume that the prover can always solve the problem".

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't understand this answer.. Can you refer specifically to the graph isomorphism example in the question? $\endgroup$
    – derek
    Jan 27, 2016 at 22:29
  • $\begingroup$ I just did that. ​ ​ $\endgroup$
    – user991
    Jan 27, 2016 at 22:39
0
$\begingroup$

I think what confuses you is that you are mixing two types of statements. Namely, statements of the type: "$G_1$ and $G_2$ are isomorphic" (I.e., the problem of graph isomorphism) and statements of the type "$G_1$ and $G_2$ are NOT isomorphic" (this is the problem called graph non-isomorphism). These are in fact two very different problems. As you point out in your question it is very easy to see how to prove statements of the former kind, but hard to prove statements of the latter kind.

You see, proving and disproving something is not the same thing. In other words, in an interactive proof the prover is only required to be able to prove true statements. Not to disprove false statements.

Improve this answer
$\endgroup$
5
  • $\begingroup$ So we assume that $G_1$ and $G_2$ are always isomorphic? And the prover isn't allowed to say "these two graphs aren't isomorphic"? $\endgroup$
    – derek
    Jan 27, 2016 at 23:34
  • $\begingroup$ @derek : ​ ​ ​ No, we just need (1+)2 properties: ({efficient verifier},) {if the verifier's input is a YES instance then the prover can reliably convince the verifier}, and {if the verifier's input is a NO instance then the verifier is overwhelmingly likely to reject (regardless of what the prover does)}. ​ The prover is allowed to say that. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user991
    Jan 27, 2016 at 23:51
  • $\begingroup$ I'm still confused though.. Take the first case - the verifier's input is a YES instance - but the prover says No. We'd have no way of knowing whether he's lying or not. Doesn't that render the whole thing useless? $\endgroup$
    – derek
    Jan 27, 2016 at 23:53
  • $\begingroup$ That doesn't "render the whole thing useless". ​ ​ $\endgroup$
    – user991
    Jan 27, 2016 at 23:56
  • $\begingroup$ Well, you could think of it like that. But the point is that the prover is only required to produce a convincing proof if the statement is true, I.e, if the graphs are isomorphic. If the statement is false the provers behavior is undefined. By the soundness property he can at least not provide a convincing proof that a false statement is true though. On the other hand the provers lack of ability to provide a convincing proof can not be seen as a convincing proof that the statement is false. $\endgroup$
    – Guut Boy
    Jan 27, 2016 at 23:57
0
$\begingroup$

When discussing interactive proof systems, it is important to precisely describe the proving and the verification procedures. The goals being that, for the special case of graph non-isomorphism on two input graphs $G_1$ and $G_2$:

  1. If $G_1$ and $G_2$ are not isomorphic and the prover and verifier follow their assigned procedures correctly, the verifier will accept that the graphs are non-isomorphic (possibly, except with negligible probability). This is called completeness.

  2. If $G_1$ and $G_2$ are isomorphic and the verifier correctly follows his verification procedure, then no matter what the prover does, the verifier will not accept that they are non-isomorphic, except with negligible probability. This is called soundness.

So, if you consider a trivial interaction wherein the prover always says "these graphs are not isomorphic" and the verifier always accepts, this is not a proof system for graph non-isomorphism, because it does not satisfy the soundness condition. To see an interactive proof for graph non-isomorphism, see the textbook of Goldreich (Section 4.2).

Improve this answer
$\endgroup$

Your Answer

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

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