Paper 2016/610 Original: eprint.iacr.org/2016/610 ↗
The GGM Function Family is Weakly One-Way
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
- Preprint.
- History
- 2016-09-12: last updated
- 2016-06-14: published
- Short URL
- https://ia.cr/2016/610
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2016/610}
}