## Cryptology ePrint Archive: Report 2002/110

The GGM Construction does NOT yield Correlation Intractable Function Ensembles

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.

Category / Keywords: foundations / Pseudorandomness, correlation intractable functions

Publication Info: To be also posted on ECCC.