# On the Generic Insecurity of the Full Domain Hash

## Yevgeniy Dodis and 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 $\F$ of trapdoor permutations ($\tdp$), where the signature of
$m$ is computed as $f^{-1}(h(m))$ (here $f\rand\F$ and $h$ is modelled
as a random oracle). It is known to be existentially unforgeable for
any $\tdp$ family $\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 $\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 $\H$ such that the corresponding schemes can be proven
secure * in the standard model*}, under some natural assumption on
the family $\F$. Our main result * rules out*} the existence of such
instantiations for * any*} assumption on $\F$ which (1) is satisfied
by a family of random permutations; and (2) does not allow the
attacker to invert $f\rand\F$ on an a-priori unbounded number of
points. Moreover, this holds even if the choice of $\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 $\F$ than what is sufficient
for the best proof of security in the random oracle model.