DS ⇒ OWF

Fully-black-box reduction · standard model · Rom90 · security loss: tight: one inverter call, and the forger succeeds whenever the inverter does, with no signing query

Statement

If a perfectly correct EUF-CMA-unforgeable signature scheme exists, so does a one-way function: $f(r):=\mathsf{vk}$, where $(\mathsf{sk},\mathsf{vk}):=\mathsf{KeyGen}(1^{\lambda };r)$, is one-way — Rom90.

Sketch

Given $\mathsf{vk}$, an inverter returns $r^{\prime }$ with $\mathsf{KeyGen}(1^{\lambda };r^{\prime })=({\mathsf{sk}}^{\prime },\mathsf{vk})$, and perfect correctness makes $\mathsf{Sign}({\mathsf{sk}}^{\prime },m)$ verify under $\mathsf{vk}$ for every $m$: a forgery with no signing query. A forger therefore succeeds with at least the inverter’s probability, which unforgeability makes negligible.

Notes

• Conversely, one-way functions give EUF-CMA-unforgeable signatures (OWF ⇒ DS) — Rom90.