Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-047 | 3rd August 2002 00:00

The GGM Construction does NOT yield Correlation Intractable Function Ensembles.

RSS-Feed




TR02-047
Authors: Oded Goldreich
Publication: 5th August 2002 11:46
Downloads: 854
Keywords: 


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.



ISSN 1433-8092 | Imprint