Full Domain Hash

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.

Security

In the random oracle model, if RSA is $(t', \epsilon')$ -secure, then the full domain hash RSA signature scheme is $(t, \epsilon)$ -secure where,

: $\begin{align}
t &= t' - (q_\text{hash} + q_\text{sig} + 1) \cdot \mathcal{O}\left(k^3\right) \\
\epsilon &= \left(1 + \frac{1}{q_\text{sig}}\right)^{q_\text{sig} + 1} \cdot q_\text{sig} \cdot \epsilon'
\end{align}$ .

For large $q_\text{sig}$ this reduces to $\epsilon \sim \exp(1)\cdot q_\text{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 $q_\text{hash}$ hashes, asks for at most $q_\text{sig}$ signatures and succeeds with probability $\epsilon$ , then there must also exist an algorithm that breaks RSA with probability $\epsilon'$ in time $t'$ .

References

Jean-Sébastien Coron(AF): On the Exact Security of Full Domain Hash. CRYPTO 2000: pp. 229–235 ([https://www.iacr.org/archive/crypto2000/18800229/18800229.pdf PDF])
Mihir Bellare, Phillip Rogaway: The Exact Security of Digital Signatures - How to Sign with RSA and Rabin. EUROCRYPT 1996: pp. 399–416 ([http://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf PDF])

Category:Digital signature schemes

Category:Theory of cryptography