The GGM Function Family Is a Weakly One-Way Family of Functions
Lists
Only you see this
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.
BibTeX
@inproceedings{cohen2016ggm,
author = {Aloni Cohen and Saleet Klein},
title = {{The GGM Function Family Is a Weakly One-Way Family of Functions}},
booktitle = {TCC (B1)},
year = {2016},
url = {https://openreview.net/forum?id=oXs5nXEI33},
}Loading related content...