Proof of knowledge

A proof of knowledge is a proof protocol whose success is linked to an efficient procedure for obtaining a cryptographic witness from the prover's behavior. The procedure is a knowledge extractor, with access to the prover specified by the definition. The ordinary verifier in an interactive proof need not receive the witness during the real exchange.^[ref]

A standard formulation measures a prover's acceptance probability $p(x)$ against a knowledge error $\kappa (x)$. When $p(x)>\kappa (x)$ on an input with a witness, extraction has an expected-time bound of the formfor an appropriate fixed constant $c$. The relation, oracle access and false-input guarantees must also be specified; this expression alone is not the complete definition.^[ref]

For an explicit graph-isomorphism proof protocol extraction, suppose the same commitment graph $H$ has accepting responsesto the two possible challenges. The compositionis a graph isomorphism, hence a witness for the public claim. Rewinding in cryptographic proofs can provide the extractor with differently challenged continuations of a common earlier state.

The formula explains a knowledge claim without invoking a human notion of understanding. Soundness of an interactive proof and zero-knowledge proof privacy are separate requirements: excluding false statements and hiding information do not by themselves establish extraction.

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.

The knowledge error $\kappa (x)$ of a proof of knowledge is a threshold in its extraction guarantee. If a prover's acceptance probability $p(x)$ exceeds that threshold, the definition requires a knowledge extractor with an appropriate expected extraction time. It is not simply the probability that the extractor outputs an incorrect witness.^[ref]

In one standard formulation, on an input in the witness relation's domain,where $C$ is an appropriate polynomial. The extraction guarantee includes the relation and oracle-access conditions as well as this bound.^[ref]

For an original numerical comparison, set $\kappa =1/2$. Acceptance probability $p=0.6$ leaves a gap of0.1, giving a factor10 multiplying $C(|x|)$ in this bound. At $p=0.51$, the factor is100. As success approaches the threshold, the permitted expected running time worsens. At $p=\kappa$, this displayed guarantee does not apply.

The single-challenge graph-isomorphism proof protocol illustrates why a nonzero threshold can be meaningful. A strategy can prepare a relabeling of one public graph and answer only its corresponding challenge, succeeding with probability $1/2$ without using an isomorphism between the two public graphs. Success beyond that baseline is what the extraction analysis exploits.^[ref]

A knowledge extractor is the algorithm that turns sufficiently successful proving behavior into a valid cryptographic witness in the definition of a proof of knowledge. The definition specifies its access to the prover and its efficiency guarantee, often in terms of acceptance probability above a knowledge error. The real verifier need not execute the extractor or learn the witness.^[ref]

A concrete algebraic step appears in the graph-isomorphism proof protocol. Suppose two accepting continuations with the same commitment $H$ supply mappingsThe extractor returnsTo check it, take any edge of $G_0$. The first mapping sends it to an edge of $H$, and the inverse second mapping sends that edge to an edge of $G_1$. Both mappings are bijections, so their composition is a graph isomorphism. The same argument handles nonedges.

This verifies the output once the two continuations have been obtained. A full extraction proof must also justify obtaining them, for example through permitted rewinding in cryptographic proofs, within the promised expected extraction time.

A zero-knowledge simulator solves a different task: it reproduces a verifier-view distribution without the witness. An extractor produces a witness from successful proving behavior. Confusing those output requirements would obscure both the privacy and knowledge guarantees.

The expected extraction time of a knowledge extractor is the expected value of its running time over the randomness in the extraction experiment. The definition specifies the extractor's access to a prover and the cryptographic witness it must return. A common proof of knowledge formulation bounds that expectation, on valid inputs and for acceptance probability $p(x)$ above knowledge error $\kappa (x)$, bywhere $C$ is a fixed polynomial. The access and output conditions are essential parts of the definition.^[ref]

An original asymptotic comparison makes the denominator meaningful. Write $n=|x|$ and suppose $C(n)=n^3$. A gap $p-\kappa =n^{-2}$ gives an expected bound $n^5$. A gap $p-\kappa =2^{-n}$ instead gives $n^3{2}^n$. The displayed extraction theorem therefore does not promise polynomial time uniformly for arbitrarily tiny positive gaps.

An expected bound also permits rare long executions. As a separate toy running-time distribution, let $T=1$ with probability $1-2^{-n}$ and $T=2^n$ with probability $2^{-n}$. Thenalthough the worst-case execution is exponential. This distribution illustrates the distinction; it is not itself an extraction construction. Markov's inequality turns an expected bound into the tail estimate $\mathrm{Pr}(T\ge a\mathbb{E}[T])\le 1/a$ for $a>0$. Converting an extractor into a procedure with a fixed deadline must account for the resulting probability of stopping before it finds a witness.