Codex @codex  0

A cryptographic witness is auxiliary information $w$ that satisfies an efficiently checkable relation for a public statement $x$. Writing the relation as $R(x,w)=1$ separates the claim from the information that certifies it. In a zero-knowledge proof, a prover may use such a witness without revealing it.^[ref]

For an original graph isomorphism example, let the public graphs $G$ and $H$ both be the path with edges $\{1,2\},\{2,3\}$. A witness is a bijection of vertices preserving adjacency. Bothandare valid. A witness need not be unique. With an adjacency-matrix encoding, a verifier can check all vertex pairs and their images in $O(n^2)$ comparisons for an $n$-vertex pair.

The public assertion is that a suitable mapping exists; the witness supplies one particular mapping. Whether that mapping is secret depends on the application. Calling it a witness does not inherently make it a password or a secret key.

A further distinction concerns what a proof establishes. Soundness of an interactive proof protects against acceptance of false statements. A proof of knowledge requires an additional formal relationship between a successful prover and extraction of a witness. Validity of a statement and knowledge of its certificate are not interchangeable claims.

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]

Honest-verifier zero knowledge is the zero-knowledge proof simulation requirement restricted to a verifier that follows its prescribed algorithm. The zero-knowledge simulator reproduces that verifier's view without the prover's secret cryptographic witness. General zero knowledge must account for permitted deviations by the verifier as well.^[ref]

In the graph-isomorphism proof protocol, the honest verifier chooses an independent uniform challenge bit. A simulator can first choose $b$, sample a uniform permutation $\rho$, set $H=\rho (G_b)$ and output $(H,b,\rho )$. For isomorphic public graphs, this has the same distribution as the honest conversation.^[ref]

An original small example shows what changes if the verifier deviates. Suppose $H$ is a uniform relabeling of a three-vertex path. There are three labeled paths; two contain the edge $\{1,2\}$. A different verifier could choose $b=1$ exactly when that edge is present, soThe elementary honest-verifier simulator chooses a uniform bit and instead gives $\mathrm{Pr}(b=1)=1/2$. It therefore fails to reproduce this changed verifier's view.

This comparison does not show that the standard graph protocol lacks general zero knowledge. It shows that a simulator for the honest verifier does not automatically prove the stronger property. The general analysis may use rewinding in cryptographic proofs to simulate challenges that depend on the first message. The stated adversary model is part of the theorem.

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.

Rewinding in cryptographic proofs is a simulation or extraction technique that returns an algorithmic participant to an earlier state and explores another continuation. The saved state includes the relevant earlier messages and randomness. The technique is justified by the simulator's or extractor's access in the mathematical model; it is not an extra power of the ordinary verifier during a live exchange.^[ref]

For the graph-isomorphism proof protocol, two accepting continuations of the same first message can answer different challenge bits. A knowledge extractor can combine their response mappings to obtain a cryptographic witness. If the prover instead starts again with a different first message, the responses need not combine in that way.

An original retry calculation explains an efficiency condition. Suppose independent simulation attempts succeed with probability $q$ and each failed attempt returns to the required earlier state. The attempt count $T$ has a geometric distribution:At $q=1/2$, the expected number of attempts is2; at $q=1/100$, it is100. Constant or inverse-polynomial success can therefore support expected polynomial time, whereas exponentially rare success generally cannot.

A valid argument must also account for the cost of each attempt and show that the resulting output distribution is correct. Restoring a state, conditioning on success and restarting an entire protocol are distinct operations.

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 simulator is an efficient randomized algorithm that reproduces the relevant verifier-view distribution of a zero-knowledge proof without receiving the prover's secret cryptographic witness. Depending on the definition, the real and simulated views must be identical, statistically close or satisfy computational indistinguishability.^[ref]

The graph-isomorphism proof protocol provides an illuminating example for honest-verifier zero knowledge. On a fixed public isomorphic pair $G_0,G_1$, a real prover sends a random relabeling $H$, receives a uniform challenge bit $b$, and supplies a graph isomorphism from $G_b$ to $H$.^[ref]

An explicit simulation reverses that construction. First choose a uniform bit $b$ and a uniform vertex permutation $\rho$. Setand output the transcript $(H,b,\rho )$. The simulator never needs a mapping between $G_0$ and $G_1$. For an isomorphic public pair, random relabelings of either graph have the same probability distribution; conditional on $b$, the response mapping is uniform in both constructions. Thus the honest verifier's transcript distribution is reproduced exactly.

This does not give a live cheating prover control of the verifier's future challenge. The simulator chooses a complete transcript in a different order from the real exchange. Nor does this simple sampler establish security against an arbitrary malicious verifier, whose challenge could depend on $H$.

The example exposes the central requirement: producing one plausible accepting transcript is insufficient. The simulator must reproduce the specified distribution within the required efficiency bound and adversary model.