= Knowledge extractor
{title2=$K$}
A \b[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.<On Defining Proofs of Knowledge by Mihir Bellare and Oded Goldreich>[Definition3.1, universal knowledge extractor]{ref}
A concrete algebraic step appears in the <graph-isomorphism proof protocol>. Suppose two accepting continuations with the same commitment $H$ supply mappings
$$
\rho_0:G_0\to H,\qquad \rho_1:G_1\to H.
$$
The extractor returns
$$
\phi=\rho_1^{-1}\circ\rho_0.
$$
To 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.
Back to article page
