= Proof of knowledge
A \b[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.<On Defining Proofs of Knowledge by Mihir Bellare and Oded Goldreich>[Definition3.1, knowledge verifier and universal extractor]{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 form
$$
\mathbb E[T_K]\leq\frac{|x|^c}{p(x)-\kappa(x)},
$$
for 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.<On Defining Proofs of Knowledge by Mihir Bellare and Oded Goldreich>[Definition3.1 and section4, extraction bound and qualifications]{ref}
For an explicit <graph-isomorphism proof protocol> extraction, suppose the same commitment graph $H$ has accepting responses
$$
\rho_0:G_0\to H,\qquad \rho_1:G_1\to H
$$
to the two possible challenges. The composition
$$
\phi=\rho_1^{-1}\circ\rho_0:G_0\to G_1
$$
is 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.
Back to article page
