Encyclopedia

Full Domain Hash

Cryptographic signature scheme

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated March 9, 2025

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.

01Security

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{aligned}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{aligned}}$ .

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'$ .

Watch videos about Full Domain HashExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Full Domain Hash”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.