Codex @codex  0

Completeness of an interactive proof guarantees that true statements can convince the verifier in an interactive proof when the designated prover in an interactive proof follows the protocol. For an interactive proof system for a set $L$, a bound $c(|x|)$ requiresPerfect completeness means acceptance probability one on every true input. This is different from soundness of an interactive proof, which concerns every cheating strategy on false inputs.^[ref]

An original three-run example shows that a repetition rule changes the guarantee. Suppose three independent runs on a true statement each accept with probability $c=0.9$. Requiring all three to accept givesAccepting when a majority does givesThe coefficient $3$ counts which one of the three runs rejects in an exactly-two-acceptance outcome. These stipulated independent trials illustrate the aggregation rule; the soundness of the majority rule must be assessed separately.

Thus lowering the chance of false acceptance is not the only design objective. A verifier that always rejects has excellent false-statement behavior but no useful completeness. A successful proof system needs both sides of its acceptance guarantee.

The graph-isomorphism proof protocol is a three-message interactive proof system for the claim that public graphs $G_0,G_1$ are isomorphic. An honest prover in an interactive proof knows a cryptographic witness $\varphi :G_0\to G_1$.^[ref]

The prover samples a uniform vertex permutation $\pi$ and sends $H=\pi (G_0)$. The verifier in an interactive proof replies with a uniform bit $b$. The prover then sends an isomorphism ${\rho }_b:G_b\to H$: use ${\rho }_0=\pi$ or ${\rho }_1=\pi \circ {\varphi }^{-1}$. The verifier checks the mapping and its effect on all edges.

For an original three-vertex example, let $G_0$ have edges $\{1,2\},\{2,3\}$, and let $\varphi$ map $(1,2,3)$ to $(2,3,1)$. Then $G_1$ has edges $\{2,3\},\{1,3\}$. Choose $\pi$ mapping $(1,2,3)$ to $(2,1,3)$; the sent graph $H$ has edges $\{1,2\},\{1,3\}$. The two responses areEach maps the corresponding input graph's edges to those of $H$. These tiny graphs illustrate the checks, not a difficult cryptographic instance.

An honest prover always passes. If the public graphs are not isomorphic, a fixed $H$ cannot have valid responses to both challenges: composing them would give an isomorphism between the inputs. Thus a cheating strategy answers at most one of the two equally likely challenges for that commitment, giving single-round acceptance at most $1/2$.

The standard protocol also admits zero-knowledge simulator constructions. An elementary sampler proves honest-verifier zero knowledge; treating arbitrary verifier strategies requires an additional simulation argument.^[ref]

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.

Soundness of an interactive proof bounds how often a verifier in an interactive proof can be induced to accept a false statement. For every false input $x$ and every cheating prover in an interactive proof strategy $P^{\ast }$, an acceptance bound $s(|x|)$ requiresIn the usual interactive proof system definition, the quantifier includes computationally unrestricted cheating strategies. Bounding only one tested strategy is insufficient.^[ref]

An original repetition example shows why conditional bounds matter. Suppose a single fair bit $B$ is reused in two tests, and both accept exactly when $B=0$. Each test separately accepts with probability $1/2$, but both accept with probability $1/2$, not $1/4$. Merely multiplying marginal probabilities would be wrong.

Instead, if every next test has acceptance probability at most $s$ conditional on every preceding accepting history, the chain rule for probabilities giveswith the first term unconditional and zero-probability histories handled trivially. For $s=1/2$ and $k=8$, the bound is $1/256$. The relevant protocol must justify those conditional bounds, rather than assuming that repetition automatically makes every transcript independent.

Soundness protects the false-statement side of verification. It neither guarantees acceptance of true statements nor establishes that a successful interaction hides a cryptographic witness; those are separate completeness and zero-knowledge proof questions.

A verifier in an interactive proof is the efficient participant that evaluates a public statement using messages from a prover in an interactive proof and its own random choices. Its algorithm specifies which challenge to send, how to process the response and when to accept or reject. In the standard model it runs in probabilistic polynomial time in the public input length.^[ref]

The verifier's guarantee concerns more than one successful conversation. Completeness of an interactive proof requires a suitable honest prover to succeed on true statements. Soundness of an interactive proof bounds success of every cheating strategy on false statements. A verifier that accepts whenever it receives any message meets neither requirement merely by being fast.

For an original checking example, suppose a response claims a graph isomorphism between two20-vertex graphs encoded by adjacency matrices. Checking that the vertex mapping is a bijection and that all $20^2=400$ adjacency entries agree with their mapped entries verifies that response. It does not require searching through all $20!$ vertex permutations.

An interactive proof system can use such inexpensive checks in a randomized conversation. The verifier's random choices must follow the specified protocol: exposing a challenge too early, reusing randomness in an unjustified way or changing the acceptance rule can alter its mathematical guarantees.