Full Domain Hash

From Wikipedia, the free encyclopedia

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.

[edit] Exact security of full domain hash

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

For large $q s i g$ this boils down to $\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 $q h a s h$ hashes, asks for at most $q s i g$ signatures and succeeds with probability $ε$ , then there must also exist an algorithm that breaks RSA with probability $ε'$ in time $t'$ .