CryptoDB
A Relationship between One-Wayness and Correlation Intractability
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-1999-11332,
title={A Relationship between One-Wayness and Correlation Intractability},
booktitle={IACR Eprint archive},
keywords={One-way functions, correlation intractability, zero-knowledge, interactive proofs, round complexity, random oracle.},
url={http://eprint.iacr.org/1999/010},
note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. hada@lab.kdd.co.jp 10500 received March 31, 1999. An earlier version has appeared in PKC'99.},
author={Satoshi Hada and Toshiaki Tanaka},
year=1999
}