**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

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]