Cryptology ePrint Archive: Report 1999/010

A Relationship between One-Wayness and Correlation Intractability

Satoshi Hada and Toshiaki Tanaka

Abstract: The notion of correlation intractability was introduced in an attempt to capture the ``unpredictability" property of random oracles: It is assumed that if $R$ is a random oracle then it is infeasible to find an input $x$ such that the input-output pair $(x,R(x))$ has some desired property. It is desirable that a plausible construction of correlation intractable function ensembles will be provided since the unpredictability property is often useful to design many cryptographic applications in the random oracle model. However, no plausibility result has been proposed. In this paper, we show that proving the implication, ``if uniform one-way functions exist then uniform correlation intractable function ensembles exist", is as hard as proving a claim regarding the triviality of 3-round auxiliary-input zero-knowledge Arthur-Merlin proofs without making any assumptions. We believe that it is unlikely that one can prove it unconditionally. Therefore, we conclude that it will be difficult to construct uniform correlation intractable function ensembles based solely on uniform one-way functions.

Category / Keywords: One-way functions, correlation intractability, zero-knowledge, interactive proofs, round complexity, random oracle.

Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.

Date: received March 31, 1999. An earlier version has appeared in PKC'99.

Contact author: hada at lab kdd co jp

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Short URL: ia.cr/1999/010

Discussion forum: Show discussion | Start new discussion