TDP ⇒ DS (full-domain hash, random oracle model)

Fully-black-box reduction · random oracle model · BR93 · security loss: a factor q_H + 1 for q_H hash queries: a forger with success ε inverts the permutation with probability ε/(q_H + 1)

Statement

Let $f$ be a trapdoor permutation of a domain $\mathcal{D}$ and $H$ a random oracle with uniform values in $\mathcal{D}$. The full-domain-hash scheme $\mathsf{Sign}(\mathsf{td},m):=f^{-1}(H(m))$, $\mathsf{Vrfy}(f,m,\sigma ):=[f(\sigma )=H(m)]$ is EUF-CMA-unforgeable in the random-oracle model — BR93.

Sketch

The reduction, given $f$ and a challenge $y$, guesses which of the forger’s hash queries will be its forgery’s message and answers that query with $y$. Every other query $m$ it answers with $f(x_m)$ for a uniform $x_m$ it stores, so it can answer a signing query on $m$ with $x_m$. A forgery on the guessed message is $f^{-1}(y)$ — BR93.

Notes

• Efficiency: signing is one inversion and verification one evaluation of $f$ plus a hash; with RSA, verification with a small public exponent costs a few modular multiplications — standard.
• Without random oracles, signatures follow from any one-way function (OWF ⇒ DS), at much higher cost — Rom90.