Aloni Cohen: GGM is a Weakly One-Way Family of Functions
Friday, February 19, 2016 - 10:30am to 12:00pm
Location:
MIT, Hewlett G882, 32 Vassar St, Gates Tower
Speaker:
Aloni Cohen
Seminar group:
Abstract: We prove that the for any constant $\epsilon>0$, GGM pseudo-random function
family is a $1/n^{2+\epsilon}$-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+\epsilon}$ -- \emph{even when given the secret key.} 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.'
family is a $1/n^{2+\epsilon}$-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+\epsilon}$ -- \emph{even when given the secret key.} 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.'
Joint work with Saleet Klein (Tel Aviv University)