Paper 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.

Metadata
Available format(s)
PS
Category
Foundations
Publication info
Published elsewhere. To be also posted on ECCC.
Keywords
Pseudorandomnesscorrelation intractable functions
Contact author(s)
oded @ wisdom weizmann ac il
History
2002-08-04: received
Short URL
https://ia.cr/2002/110
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/110,
      author = {Oded Goldreich},
      title = {The GGM Construction does NOT yield  Correlation Intractable Function Ensembles},
      howpublished = {Cryptology ePrint Archive, Paper 2002/110},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/110}},
      url = {https://eprint.iacr.org/2002/110}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.