Optimal Security Proofs for Full Domain Hash, Revisited

RSA Full Domain Hash (RSA-FDH) is a digital signature scheme, secure again chosen message attacks in the random oracle model. The best known security reduction from the RSA assumption is nontight, i.e., it loses a factor of q

s

, where q

s

is the number of signature queries made by the adversary. It was furthermore proved by Coron (EUROCRYPT 2002) that a security loss of q

s

is optimal and cannot possibly be improved. In this work we uncover a subtle flaw in Coron’s impossibility result. Concretely, we show that it only holds if the underlying trapdoor permutation is

certified

. Since it is well known that the RSA trapdoor permutation is (for all practical parameters) not certified, this renders Coron’s impossibility result moot for RSA-FDH. Motivated by this, we revisit the question whether there is a tight security proof for RSA-FDH. Concretely, we give a new tight security reduction from a stronger assumption, the Phi-Hiding assumption introduced by Cachin et al (EUROCRYPT 1999). This justifies the choice of smaller parameters in RSA-FDH, as it is commonly used in practice. All of our results (positive and negative) extend to the probabilistic signature scheme PSS.