zbMATH — the first resource for mathematics

The GGM construction does NOT yield correlation intractable function ensembles. (English) Zbl 1343.94052
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 98-108 (2011).
Summary: 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.
For the entire collection see [Zbl 1220.68005].

94A60 Cryptography
Full Text: DOI
[1] Canetti, R., Goldreich, O., Halevi, S.: The Random Oracle Methodology. In: 30th STOC, pp. 209–218 (1998) (revisited) · Zbl 1027.68603
[2] Goldreich, O., Goldwasser, S., Micali, S.: How to Construct Random Functions. JACM 33(4), 792–807 (1986) · Zbl 0596.65002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.