= Interactive proof system
{title2=$(P,V)$}
An \b[interactive proof system] is a protocol in which a <prover in an interactive proof> exchanges messages with a <verifier in an interactive proof> to establish a public statement. The verifier is a <randomized algorithm> running in <polynomial time>; the prover need not have that resource bound. <Completeness of an interactive proof> and <soundness of an interactive proof> specify acceptance behavior on true and false statements.<Probabilistic Proof Systems: A Primer by Oded Goldreich>[Sections1.1.2–1.2, prover/verifier model and Definition1.1]{ref}
For a <decision problem> represented by a set $L$, write the acceptance bounds as
$$
x\in L\implies\Pr[V\text{ accepts after interaction with }P]\geq c(|x|),
$$
$$
x\notin L\implies\forall P^*:\quad\Pr[V\text{ accepts after interaction with }P^*]\leq s(|x|).
$$
The first condition supplies an honest proving strategy; the second constrains every cheating strategy, including adaptive answers. The bounds need a useful separation between $c$ and $s$.
<Graph non-isomorphism> gives a concrete protocol. Given two <graphs> $G_0,G_1$ on the same number of vertices, the verifier secretly chooses a uniform bit $b$, randomly relabels $G_b$ using a <permutation>, and sends the result $H$. The prover guesses which input graph was chosen; the verifier accepts exactly when the guess equals $b$.<Probabilistic Proof Systems: A Primer by Oded Goldreich>[Construction1.3, graph non-isomorphism]{ref}
If the graphs are non-isomorphic, an unrestricted prover can identify the correct isomorphism class and always answer correctly. If they are isomorphic, the two ways of generating $H$ have identical <probability distributions>, so $H$ gives no information about $b$ and any guess succeeds with probability $1/2$. The verifier's secret random choice creates the test. This soundness argument alone makes no claim that the protocol is a <zero-knowledge proof>.
Back to article page
