Paper 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.
Metadata
- Available format(s)
- PS
- Publication info
- Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
- Keywords
- One-way functionscorrelation intractabilityzero-knowledgeinteractive proofsround complexityrandom oracle.
- Contact author(s)
- hada @ lab kdd co jp
- History
- 1999-03-31: received
- Short URL
- https://ia.cr/1999/010
- License
-
CC BY
BibTeX
@misc{cryptoeprint:1999/010,
author = {Satoshi Hada and Toshiaki Tanaka},
title = {A Relationship between One-Wayness and Correlation Intractability},
howpublished = {Cryptology ePrint Archive, Paper 1999/010},
year = {1999},
note = {\url{https://eprint.iacr.org/1999/010}},
url = {https://eprint.iacr.org/1999/010}
}
