DIMACS TR: 93-65

Instance-Hiding Proof Systems

Authors: D. Beaver, J. Feigenbaum, R. Ostrovsky, V. Shoup


We define the notion of an instance-hiding proof system (ihps) for a function f; informally, an ihps is a protocol in which a polynomial-time verifier interacts with one or more all-powerful provers and is convinced of the value of f(x) but does not reveal the input x to the provers. We show here that a function f has a multiprover ihps if and only if it is computable in FNEXP. We formalize the notion of zero-knowledge for ihps's and show that any function that has a multiprover ihps in fact has one that is perfect zero-knowledge. Under the assumption that one-way permutations exist, we show that f has a one-prover, zero-knowledge ihps if and only if it is in FPSPACE and has a one-oracle instance-hiding scheme (ihs).

The results in Sections 3 and 4 of this paper were presented in preliminary form at Crypto '90, Santa Barbara, CA, August 1990. Those in Section 5 were presented in preliminary form at Asiacrypt '91, Fujiyoshida, Japan, November 1991.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-65.ps

DIMACS Home Page