FAC ⇒ DS

Fully-black-box reduction · standard model · GMR88

Statement

If FAC is hard, an EUF-CMA-secure DS scheme exists: GMR build a stateful EUF-CMA-secure scheme from any claw-free pair of trapdoor permutations and instantiate claw-free pairs from factoring — GMR88.

Sketch

Signing authenticates the message and the path to a fresh leaf of an authentication tree with inverses of the claw-free pair $(f_0,f_1)$. The reduction turns any forgery into a claw $(x_0,x_1)$ with $f_0(x_0)=f_1(x_1)$, which for the factoring-based pair, built from squaring modulo $N$, reveals a nontrivial square root of $1$ modulo $N$ and hence the factorization of $N$.