----------------------
Title: The GGM PRF is a Weakly One-Way Family of Functions
Abstract: We give the first demonstration of a cryptographic hardness property of the Goldreich-Goldwasser-Micalli (GGM) pseudo-random function family with exposed key. We prove that for any constant epsilon > 0, the GGM pseudo-random function family is a 1/n2+epsilon-weakly one-way family of functions, when the lengths of seeds, inputs, and outputs are equal. Namely, any efficient algorithm fails to invert GGM with probability at least 1/n2+epsilon – even when given the secret key. Along the way, we prove a purely combinatorial lemma for ’GGM-like’ functions, relating the size of the image of such functions to the statistical distance between certain ’sub-functions.’