
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

ZeroKnowledge and Correlation Intractability
Satoshi HADA Toshiaki TANAKA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E89A
No.10
pp.28942905 Publication Date: 2006/10/01
Online ISSN: 17451337
DOI: 10.1093/ietfec/e89a.10.2894
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Information Security Keyword: oneway functions, correlation intractability, zeroknowledge, interactive proofs, round complexity, random oracle,
Full Text: PDF>>
Summary:
The notion of correlation intractable function ensembles (CIFEs) was introduced in an attempt to capture the "unpredictability" property of random oracles [12]: If O is a random oracle then it is infeasible to find an input x such that the inputoutput pair (x,O(x)) has some desired property. In this paper, we observe relationships between zeroknowledge protocols and CIFEs. Specifically, we show that, in the nonuniform model, the existence of CIFEs implies that 3round auxiliaryinput zeroknowledge (AIZK) AM interactive proofs exist only for BPP languages. In the uniform model, we show that 3round AIZK AM interactive proofs with perfect completeness exist only for easytoapproximate languages. These conditional triviality results extend to constantround AIZK AM interactive proofs assuming the existence of multiinput CIFEs, where "multiinput" means that the correlation intractability is satisfied with respect to multiple inputoutput pairs. Also, as a corollary, we show that any construction of uniform multiinput CIFEs from uniform oneway functions proves unconditionally that constantround AIZK AM interactive proofs with perfect completeness only for easytoapproximate languages.

