Fandom

DSZQUP XJLJ

Full Domain Hash

566pages on
this wiki
Add New Page
Talk0 Share

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.

Exact security of full domain hashEdit

In the random oracle model, if RSA is (t',\epsilon')-secure, then the full domain hash RSA signature scheme is (t,\epsilon)-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_{sig} 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_{hash} hashes, asks for at most q_{sig} signatures and succeeds with probability \epsilon, then there must also exist an algorithm that breaks RSA with probability \epsilon' in time t'.

ReferencesEdit

  • Jean-Sébastien Coron: On the Exact Security of Full Domain Hash. CRYPTO 2000: pp229–235 (PDF)

de:Full-Domain-Hash

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.