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)