Zero-Knowledge and Correlation Intractability

Abstract

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 inputx such that the input-output pair (x,O(x)) has some desired property. In this paper, we observe relationships between zero-knowledge protocols and CIFEs. Specifically, we show that, in the non-uniform model, the existence of CIFEs implies that 3-round auxiliary-input zero-knowledge (AIZK) AM interactive proofs exist only for BPP languages. In the uniform model, we show that 3-round AIZK AM interactive proofs with perfect completeness exist only for easy-to-approximate languages. These conditional triviality results extend to constant-round AIZK AM interactive proofs assuming the existence of CIFEs, where multi-input means that the correlation intractability is satisfied with respect to multiple input-output pairs. Also, as a corollary, we show that any construction of uniform CIFEs from uniform one-way functions proves unconditionally that constant-round AIZK AM interactive proofs with perfect completeness only for easy-to-approximate languages.