International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

The GGM Construction does NOT yield Correlation Intractable Function Ensembles

Authors:
Oded Goldreich
Download:
URL: http://eprint.iacr.org/2002/110
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2002-11633,
  title={The GGM Construction does NOT yield  Correlation Intractable Function Ensembles},
  booktitle={IACR Eprint archive},
  keywords={foundations / Pseudorandomness, correlation intractable functions},
  url={http://eprint.iacr.org/2002/110},
  note={To be also posted on ECCC. oded@wisdom.weizmann.ac.il 11903 received 4 Aug 2002},
  author={Oded Goldreich},
  year=2002
}