ID ⇒ OWF

Fully-black-box reduction · standard model · IL89 · security loss: polynomial

Statement

If an identification scheme secure against impersonation exists, then a one-way function exists — IL89.

Sketch

The one-way function is $f(r)=\mathsf{pk}$ for $(\mathsf{pk},\mathsf{sk})\leftarrow \mathsf{KeyGen}(1^{\lambda };r)$. If one-way functions do not exist, $f$ is not even distributionally one-way, so for infinitely many $\lambda$ an efficient inverter returns coins $r^{\prime }$ nearly uniform among the preimages of $\mathsf{pk}$; the secret key output by $\mathsf{KeyGen}(1^{\lambda };r^{\prime })$ is then distributed almost as the prover’s secret key given $\mathsf{pk}$, and the impersonator runs the honest prover with it — IL89.

Notes

• Signature schemes are treated the same way: DS ⇒ OWF — Rom90.