In cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, the Full Domain Hash (FDH) is an RSA-based signature

Digital signature

A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...

 scheme that follows the hash-and-sign paradigm. It is provably secure

Provable security

In cryptography, a system has provable security if its security requirements can be stated formally in an adversarial model, as opposed to heuristically, with clear assumptions that the adversary has access to the system as well as enough computational resources...

 (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 hash

In the random oracle model, if RSA is -secure, then the full domain hash RSA signature scheme is -secure where, and
.

For large this boils down to .

This means that if there exists an algorithm that can forge a new FDH signature that runs in time t, computes at most hashes, asks for at most signatures and succeeds with probability , then there must also exist an algorithm that breaks RSA with probability in time .