The knowledge error of a proof of knowledge is a threshold in its extraction guarantee. If a prover's acceptance probability 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]
On Defining Proofs of Knowledge by Mihir Bellare and Oded Goldreich. Definition3.1, knowledge-error function and validity condition
In one standard formulation, on an input in the witness relation's domain,where is an appropriate polynomial. The extraction guarantee includes the relation and oracle-access conditions as well as this bound.[ref]
On Defining Proofs of Knowledge by Mihir Bellare and Oded Goldreich. Definition3.1 and section4, qualifications to the extraction condition
For an original numerical comparison, set . Acceptance probability leaves a gap of0.1, giving a factor10 multiplying in this bound. At , the factor is100. As success approaches the threshold, the permitted expected running time worsens. At , 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 without using an isomorphism between the two public graphs. Success beyond that baseline is what the extraction analysis exploits.[ref]
On Defining Proofs of Knowledge by Mihir Bellare and Oded Goldreich. Section4.4, graph-isomorphism example and knowledge error1/2
New to topics? Read the docs here!