Information Security and Cryptography Research Group

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

Files and Links

• PDF
• PS