## 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}, }