Cryptology ePrint Archive: Report 2002/110
The GGM Construction does NOT yield Correlation Intractable Function Ensembles
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.
Date: received 4 Aug 2002
Contact author: oded at wisdom weizmann ac il
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Version: 20020804:220237 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]