DIMACS TR: 93-65
Instance-Hiding Proof Systems
Authors: D. Beaver, J. Feigenbaum, R. Ostrovsky, V. Shoup
ABSTRACT
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