Paper 2015/334

On the Correlation Intractability of Obfuscated Pseudorandom Functions

Ran Canetti, 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].

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in TCC 2016
Contact author(s)
canetti @ tau ac il
chenyl @ bu edu
reyzin @ cs bu edu
History
2015-11-17: last of 3 revisions
2015-04-19: received
See all versions
Short URL
https://ia.cr/2015/334
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/334,
      author = {Ran Canetti and Yilei Chen and Leonid Reyzin},
      title = {On the Correlation Intractability of Obfuscated Pseudorandom Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/334},
      year = {2015},
      url = {https://eprint.iacr.org/2015/334}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.