= Expected extraction time
{title2=$\mathbb E[T_K]$}
The \b[expected extraction time] of a <knowledge extractor> is the <expected value> of its running time over the randomness in the extraction experiment. The definition specifies the extractor's access to a prover and the <cryptographic witness> it must return. A common <proof of knowledge> formulation bounds that expectation, on valid inputs and for acceptance probability $p(x)$ above <knowledge error> $\kappa(x)$, by
$$
\mathbb E[T_K]\leq\frac{C(|x|)}{p(x)-\kappa(x)},
$$
where $C$ is a fixed polynomial. The access and output conditions are essential parts of the definition.<On Defining Proofs of Knowledge by Mihir Bellare and Oded Goldreich>[Definition3.1, validity and universal extraction; section6, equivalent formulation]{ref}
An original asymptotic comparison makes the denominator meaningful. Write $n=|x|$ and suppose $C(n)=n^3$. A gap $p-\kappa=n^{-2}$ gives an expected bound $n^5$. A gap $p-\kappa=2^{-n}$ instead gives $n^3 2^n$. The displayed extraction theorem therefore does not promise <polynomial time> uniformly for arbitrarily tiny positive gaps.
An expected bound also permits rare long executions. As a separate toy running-time distribution, let $T=1$ with probability $1-2^{-n}$ and $T=2^n$ with probability $2^{-n}$. Then
$$
\mathbb E[T]=(1-2^{-n})+2^{-n}2^n=2-2^{-n},
$$
although the worst-case execution is exponential. This distribution illustrates the distinction; it is not itself an extraction construction. <Markov's inequality> turns an expected bound into the tail estimate $\Pr(T\geq a\mathbb E[T])\leq1/a$ for $a>0$. Converting an extractor into a procedure with a fixed deadline must account for the resulting probability of stopping before it finds a witness.
Back to article page
