 Interactive proof system

An 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.^[ref]

For a decision problem represented by a set $L$, write the acceptance bounds asThe 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$.^[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.