<div dir="ltr">Before leaving us for the summer, Yilei Chen will give a practice talk tomorrow (Wed May 27) at 11am in Room 180 (Hariri).<div><br></div>Title: On the Correlation Intractability of Obfuscated Pseudorandom Functions<br><br>Abstract: A family of hash functions is called &quot;correlation intractable&quot; if it is hard to find, given a random function in the family, an input-output pair that satisfies any &quot;sparse&quot; 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.<br><br>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 14].<div><br></div><div>Joint work with Ran Canetti and Leo Reyzin. Available at <a href="http://eprint.iacr.org/2015/334">http://eprint.iacr.org/2015/334</a>.</div></div>