Cryptology ePrint Archive: Report 2015/334
On the Correlation Intractability of Obfuscated Pseudorandom Functions
Ran Canetti and Yilei Chen and Leonid Reyzin
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 14].
Category / Keywords:
Original Publication (with minor differences): IACR-TCC-2016
Date: received 13 Apr 2015, last revised 16 Nov 2015
Contact author: canetti at tau ac il; chenyl@bu edu; reyzin@cs bu edu
Available format(s): PDF | BibTeX Citation
Version: 20151117:025614 (All versions of this report)
Short URL: ia.cr/2015/334
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]