Full Domain Hash

☆ Save On Wikipedia ↗

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 ′ , ϵ ′ ) {\displaystyle (t',\epsilon ')} {\displaystyle (t',\epsilon ')}-secure, then the full domain hash RSA signature scheme is ( t , ϵ ) {\displaystyle (t,\epsilon )} {\displaystyle (t,\epsilon )}-secure where,

t = t ′ − ( q hash + q sig + 1 ) ⋅ O ( k 3 ) ϵ = ( 1 + 1 q sig ) q sig + 1 ⋅ q sig ⋅ ϵ ′ {\displaystyle {\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}}} {\displaystyle {\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 sig {\displaystyle q_{\text{sig}}} {\displaystyle q_{\text{sig}}} this reduces to ϵ ∼ exp ⁡ ( 1 ) ⋅ q sig ⋅ ϵ ′ {\displaystyle \epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '} {\displaystyle \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 hash {\displaystyle q_{\text{hash}}} {\displaystyle q_{\text{hash}}} hashes, asks for at most q sig {\displaystyle q_{\text{sig}}} {\displaystyle q_{\text{sig}}} signatures and succeeds with probability ϵ {\displaystyle \epsilon } {\displaystyle \epsilon }, then there must also exist an algorithm that breaks RSA with probability ϵ ′ {\displaystyle \epsilon '} {\displaystyle \epsilon '} in time t ′ {\displaystyle t'} {\displaystyle t'}.

References

  • 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)