OWF + iO ⇒ DS

Free reduction · standard model · SW14 · security loss: additive: the forging probability is at most the iO advantage plus the punctured-PRF advantage plus the probability of inverting the one-way function, with the punctured PRF built from the one-way function at a polynomial loss

Statement

If iO for all polynomial-size circuits and a one-way function exist, there is a signature scheme with short signatures that is selectively unforgeable under chosen-message attack: for all efficient $\mathcal{A}$ that commit to a target message $m^{\ast }$ before seeing $\mathsf{vk}$ and then query signatures on messages other than $m^{\ast }$, the probability that $\mathcal{A}$ outputs a valid signature on $m^{\ast }$ is negligible — SW14.

Sketch

The signing key is a puncturable PRF key $K$, the signature on $m$ is $F(K,m)$, and $\mathsf{vk}$ obfuscates the program accepting $(m,\sigma )$ iff $f(\sigma )=f(F(K,m))$, for a one-way function $f$. The reduction punctures $K$ at $m^{\ast }$ and hardcodes $y^{\ast }=f(F(K,m^{\ast }))$, which iO hides because the program’s input–output behavior is unchanged; punctured-PRF security then replaces $F(K,m^{\ast })$ by a uniform value, so a forgery on $m^{\ast }$ is a preimage of $y^{\ast }$ under $f$.

Notes

• One-way functions alone give adaptively EUF-CMA-unforgeable signatures (OWF ⇒ DS) — Rom90; the contribution of the iO construction is short signatures.