Aloni Cohen: GGM is a Weakly One-Way Family of Functions

Speaker: Aloni Cohen , MIT

Date: Friday, February 19, 2016

Time: 10:30 AM to 12:00 PM

Public: Yes

Location: Hewlett, G882

Event Type:

Room Description:

Host: Vinod Vaikuntanathan

Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: TALK: Aloni Cohen: GGM is a Weakly One-Way Family of Functions

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

Joint work with Saleet Klein (Tel Aviv University)

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security (CIS) Seminar Series 2016.

Created by Deborah Goodwin Email at Tuesday, February 16, 2016 at 9:09 AM.