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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2016
Keywords
Goldreich-Goldwasser-Micali (GGM)one-way functionspseudorandom functions
Contact author(s)
aloni @ mit edu
saleet @ mit edu
History
2016-09-12: last of 3 revisions
2016-06-14: received
See all versions
Short URL
https://ia.cr/2016/610
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/610,
      author = {Aloni Cohen and Saleet Klein},
      title = {The GGM Function Family is Weakly One-Way},
      howpublished = {Cryptology ePrint Archive, Paper 2016/610},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/610}},
      url = {https://eprint.iacr.org/2016/610}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.