Full Domain Hash is the simplest signature scheme based on a trapdoor permutation (such as textbook RSA) that enjoys a strict security reduction. It was introduced by Mihir Bellare and Phillip Rogaway: The Exact Security of Digital Signatures - How to Sign with RSA and Rabin (in proceedings of EuroCrypt 1996).

Bellare and Rogaway's security bound was improved by Jean-Sébastien Coron: On the Exact Security of Full Domain Hash (in proceedings of Crypto 2000) and Optimal Security Proofs for PSS and Other Signature Schemes (in proceedings of EuroCrypt 2002).

I first ask a didactic exposition of the security proof of FDH. Preferably, the improved one.

If possible: does that allow to quantify the security loss when the hash is not quite full-domain, but rather is uniformly distributed on a proportion $\alpha\in(0,1)$ of the RSA domain? E.g. if the hash is uniformly distributed on $h\lesssim\log_2N$ bits, we have $\alpha=2^h/N$ .

Update: FDH is also analyzed in Dan Boneh and Victor Shoup's A Graduate Course in Applied Cryptography.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.