GeezerVison

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.

In the random oracle model, if RSA is $(t^{\prime },{\mathrm{ϵ<!--\; ϵ\; -->}}^{\prime })$-secure, then the full domain hash RSA signature scheme is $(t,\mathrm{ϵ<!--\; ϵ\; -->})$-secure where,

.

For large $q_{\text{sig}}$ this reduces to $\mathrm{ϵ<!--\; ϵ\; -->}\sim <!--\; \sim \; -->\exp <!--\; \; -->\left(1\right)\cdot <!--\; \cdot \; -->q_{\text{sig}}\cdot <!--\; \cdot \; -->{\mathrm{ϵ<!--\; ϵ\; -->}}^{\prime }$.

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 $\mathrm{ϵ<!--\; ϵ\; -->}$, then there must also exist an algorithm that breaks RSA with probability ${\mathrm{ϵ<!--\; ϵ\; -->}}^{\prime }$ in time $t^{\prime }$.

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

This cryptography-related article is a stub. You can help Wikipedia by adding missing information.

• v
• t
• e