ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

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.