## The GGM Construction does NOT yield Correlation
Intractable Function Ensembles

#### Webpage for a paper by Oded Goldreich

#### Abstract

We consider the function ensembles emerging from the
construction of Goldreich, Goldwasser and Micali (GGM),
when applied to an arbitrary pseudoramdon generator.
We show that, in general, such functions
fail to yield correlation intractable ensembles.
Specifically, it may happen that, given a description of such a
function,
one can easily find an input that is mapped to zero under this
function.

#### Added Note (Sept 2007)

Theorem 5 asserts that for the resulting function ensemble,
with probability at least 10% over the choice of the function *f*,
one can quickly find a string *x* in the *f*-preimage of 0.
The argument can be easily modified to finding several (different)
such preimages, because the randomly-labeled tree (considered on page 5)
is likely to have several leaves in $S_\ell$ (rather than a single one).
It follows that the GGM construction also
does NOT yield collision-resilient hash functions.

#### Material available on-line

- First version posted:
July 2002.
- Revisions: none yet.

Back to
either Oded Goldreich's homepage.
or general list of papers.