Optimal Security Proofs for Full Domain Hash, Revisited
Eike Kiltz (Ruhr-Universität Bochum)
Thursday 19 January 2012, 15.00, b-it 1.25 (cosec meeting room)
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 non-tight, 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.
Joint work with Saqib Kakvi. To appear at EUROCRYPT 2012.