 Knowledge extractor

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.