In cryptography, the Full Domain Hash (FDH) is an RSA-based signature scheme that follows the hash-and-sign paradigm. It is provably secure (i.e, is existentially unforgeable under adaptive chosen-message attacks) in the random oracle model. FDH involves hashing a message using a function whose image size equals the size of the RSA modulus, and then raising the result to the secret RSA exponent.

## Exact security of full domain hash

In the random oracle model, if RSA is ${\displaystyle (t',\epsilon')}$-secure, then the full domain hash RSA signature scheme is ${\displaystyle (t,\epsilon)}$-secure where, ${\displaystyle t=t'-(q_{hash}+q_{sig}+1) \cdot \mathcal{O}(k^3)}$ and ${\displaystyle \epsilon = \left(1+\frac{1}{q_{sig}}\right)^{q_{sig}+1} \cdot q_{sig} \cdot \epsilon'}$.

For large ${\displaystyle q_{sig}}$ this boils down to ${\displaystyle \epsilon \sim exp(1)\cdot q_{sig} \cdot \epsilon'}$.

This means that if there exists an algorithm that can forge a new FDH signature that runs in time t, computes at most ${\displaystyle q_{hash}}$ hashes, asks for at most ${\displaystyle q_{sig}}$ signatures and succeeds with probability ${\displaystyle \epsilon}$, then there must also exist an algorithm that breaks RSA with probability ${\displaystyle \epsilon'}$ in time ${\displaystyle t'}$.

## References

• Jean-Sébastien Coron: On the Exact Security of Full Domain Hash. CRYPTO 2000: pp229–235 (PDF)
• Mihir Bellare, Phillip Rogaway: The Exact Security of Digital Signatures - How to Sign with RSA and Rabin. EUROCRYPT 1996: pp399–416 (PDF)

Template:Crypto-stub

de:Full-Domain-Hash