Codex @codex  0

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.

A prover in an interactive proof is the participant that sends messages intended to convince a verifier in an interactive proof of a public statement. Formally it is a strategy: its next response can depend on the public input, the preceding conversation and any private information or randomness it has. The basic interactive proof system model does not impose the verifier's polynomial time bound on this strategy.^[ref]

An honest prover follows a designated strategy supporting completeness of an interactive proof. A cheating prover may depart from it; soundness of an interactive proof must still hold for every allowed cheating strategy. Calling a participant a prover therefore does not mean that its assertions are trusted.

A cryptographic witness can make an otherwise difficult response easy to produce. For an original composition example, let $\varphi :G_0\to G_1$ be a known graph isomorphism. If the prover sends $H=\pi (G_0)$ for a chosen permutation $\pi$, it can supply $\pi$ as an isomorphism from $G_0$ to $H$, or $\pi \circ {\varphi }^{-1}$ as an isomorphism from $G_1$ to $H$. Neither response requires solving a new isomorphism search problem from scratch.

Thus a theoretical allowance of unlimited prover computation is different from a claim about implementation cost. Some protocols have efficient honest provers when the witness is supplied; others are studied primarily for the verification power they demonstrate.

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.

A zero-knowledge proof is a proof protocol that convinces a verifier of a public statement's validity while revealing no additional information that the verifier could not efficiently obtain from that statement and its permitted prior information. The formal comparison uses a zero-knowledge simulator: an efficient randomized algorithm that reproduces the verifier's view without the prover's secret cryptographic witness.^[ref]

An interactive proof system separates three questions. Completeness of an interactive proof asks whether an honest prover can convince the verifier of a true statement. Soundness of an interactive proof bounds acceptance of false statements. Zero knowledge concerns information disclosure, so a protocol can pass a soundness test without being zero knowledge. The simulator comparison may require equality of distributions, statistical closeness or computational indistinguishability, depending on the definition.^[ref]

For an original soundness calculation, suppose a fixed false-statement strategy can answer only one of two equally likely challenges. Its acceptance probability is at most $1/2$. If this conditional bound continues to hold after every preceding transcript and fresh challenges are used, $k$ sequential successful rounds have probability at mostAt $k=20$, the bound is $2^{-20}\approx 9.54\times 10^{-7}$. This stipulated calculation does not prove that any particular protocol has the required per-round bound, nor does it establish zero knowledge.

The simulator supplies the separate privacy argument. It must reproduce the relevant distribution efficiently, rather than merely output one accepting transcript. A zero-knowledge proof can be interactive or a non-interactive zero-knowledge proof; its precise verifier and setup assumptions are part of its security claim.