Cryptology ePrint Archive: Report 2016/610
The GGM Function Family is Weakly One-Way
Aloni Cohen and Saleet Klein
Abstract: We give the first demonstration of the cryptographic hardness of the Goldreich-Goldwasser-Micali (GGM) function family when the secret key is exposed. We prove that for any constant $\epsilon>0$, the GGM family is a $1/n^{2+\epsilon}$-weakly one-way family of functions, when the lengths of secret key, inputs, and outputs are equal.
Namely, any efficient algorithm fails to invert GGM with probability at least $1/n^{2+\epsilon}$, even when given the secret key.
Additionally, we state natural conditions under which the GGM family is strongly one-way.
Category / Keywords: foundations / Goldreich-Goldwasser-Micali (GGM), one-way functions, pseudorandom functions
Original Publication (with minor differences): IACR-TCC-2016
Date: received 10 Jun 2016, last revised 12 Sep 2016
Contact author: aloni at mit edu; saleet@mit edu
Available format(s): PDF | BibTeX Citation
Version: 20160912:192454 (All versions of this report)
Short URL: ia.cr/2016/610
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]