Welcome to the resource topic for 1999/010
Title:
A Relationship between One-Wayness and Correlation Intractability
Authors: Satoshi Hada, 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.
ePrint: https://eprint.iacr.org/1999/010
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .