[Busec] practice talk by Yilei Chen Wed 11am

Leonid Reyzin reyzin at cs.bu.edu
Tue May 26 14:25:58 EDT 2015

Before leaving us for the summer, Yilei Chen will give a practice talk
tomorrow (Wed May 27) at 11am in Room 180 (Hariri).

Title: On the Correlation Intractability of Obfuscated Pseudorandom

Abstract: A family of hash functions is called "correlation intractable" if
it is hard to find, given a random function in the family, an input-output
pair that satisfies any "sparse" relation, namely any relation that is hard
to satisfy for truly random functions. Correlation intractability captures
a strong and natural Random Oracle-like property. However, it is widely
considered to be unobtainable. Indeed, it was shown that correlation
intractable functions do not exist for some length parameters [Canetti,
Goldreich and Halevi, J.ACM 04]. Furthermore, no candidate constructions
have been proposed in the literature for any setting of the parameters.

We construct a correlation intractable function ensemble that withstands
all relations with a priori bounded polynomial complexity. We assume the
existence of sub-exponentially secure indistinguishability obfuscators,
puncturable pseudorandom functions, and input-hiding obfuscators for
evasive circuits. The existence of the latter is implied by
Virtual-Grey-Box obfuscation for evasive circuits [Bitansky et al, CRYPTO

Joint work with Ran Canetti and Leo Reyzin. Available at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20150526/6ab7ecb8/attachment.html>

More information about the Busec mailing list