On the Generic Insecurity of the Full Domain Hash
Yevgeniy Dodis, Roberto Oliveira, and Krzysztof Pietrzak
The Full-Domain Hash (FDH) signature scheme \cite{BR93} forms one the most basic usages of random oracles. It works with a family $\mathcal{F}$ of trapdoor permutations (TDP), where the signature of $m$ is computed as $f^{-1}(h(m))$ (here $f\in_{\mathcal R}\mathcal{F}$ and $h$ is modelled as a random oracle). It is known to be existentially unforgeable for any TDP family $\mathcal{F}$ \cite{BR93}, although a much tighter security reduction is known for a restrictive class of \tdp's \cite{Cor00,DR02} — namely, those induced by a family of claw-free permutations (CFP) pairs. The latter result was shown \cite{Cor02} to match the best possible “black-box” security reduction in the random oracle model, irrespective of the \tdp family $\mathcal{F}$ (e.g., RSA) one might use.
In this work we investigate the question if it is possible to instantiate the random oracle $h$ with a “real” family of hash functions $\mathcal{H}$ such that the corresponding schemes can be proven secure in the standard model, under some natural assumption on the family $\mathcal{F}$. Our main result rules out the existence of such instantiations for any assumption on $\mathcal{F}$ which (1) is satisfied by a family of random permutations; and (2) does not allow the attacker to invert $f\in_{\mathcal R}\mathcal{F}$ on an a-priori unbounded number of points. Moreover, this holds even if the choice of $\mathcal{H}$ can arbitrarily depend on $f$. As an immediate corollary, we rule out instantiating FDH based on general claw-free permutations, which shows that in order to prove the security of FDH in the standard model one must utilize significantly more structure on $\mathcal{F}$ than what is sufficient for the best proof of security in the random oracle model.
BibTeX Citation
@inproceedings{DoOlPi05,
author = {Yevgeniy Dodis and Roberto Oliveira and Krzysztof Pietrzak},
title = {On the Generic Insecurity of the Full Domain Hash},
booktitle = {Advances in Cryptology --- CRYPTO 2005},
pages = 449--466,
series = {Lecture Notes in Computer Science},
volume = 3621,
year = 2005,
month = 8,
publisher = {Springer-Verlag},
}