= Knowledge error
{title2=$\kappa(x)$}
The \b[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.<On Defining Proofs of Knowledge by Mihir Bellare and Oded Goldreich>[Definition3.1, knowledge-error function and validity condition]{ref}
In one standard formulation, on an input in the witness relation's domain,
$$
\mathbb E[T_K]\leq\frac{C(|x|)}{p(x)-\kappa(x)},\qquad p(x)>\kappa(x),
$$
where $C$ is an appropriate polynomial. The extraction guarantee includes the relation and oracle-access conditions as well as this bound.<On Defining Proofs of Knowledge by Mihir Bellare and Oded Goldreich>[Definition3.1 and section4, qualifications to the extraction condition]{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.<On Defining Proofs of Knowledge by Mihir Bellare and Oded Goldreich>[Section4.4, graph-isomorphism example and knowledge error1/2]{ref}
Back to article page
