The GGM PRF is a Weakly One-Way Family of Functions

We give the first demonstration of a cryptographic hardness property of the Goldreich-Goldwasser-Micali (GGM) pseudo-random function family when the secret key is exposed. We prove that for any constant c>0, the GGM family is a 1/n^{2+c}-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/n^{2+c} -- even when given the secret key. We additionally state a natural condition under which the GGM family is strongly one-way. 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'.