A Note On One-Prover, Instance-Hiding Zero-Knowledge Proof Systems.
Joan Feigenbaum, Rafail Ostrovsky
Abstract: In this note we compare two cryptographic notions introduced in recent years: zero-knowledge proof systems and instance-hiding schemes. Informally, a zero-knowledge proof system for $f$ is a protocol between two players $A$ (an infinitely powerful prover) and $B$ (a probabilistic polynomial-time verifier), with a common input $(x,y)$, in which $A$ convinces $B$ that $y=f(x)$ without revealing anything else. Informally, an instance-hiding scheme for the function $f$ is a protocol between two players $A$ (an infinitely powerful oracle) and $B$ (a probabilistic polynomial-time querier) in which $B$, who has a private input $x$, uses the superior computing power of $A$ to derive $f(x)$ without revealing to $A$ anything about $x$ except its length. In this paper, show that if one-way permutations exist, the following two statements are equivalent for any function $f$:
$f$ has a one-prover, instance-hiding, zero-knowledge proof system.
$f$ is computable in polynomial space and has an instance-hiding scheme that leaks at most the length of the input.
comment: Appeared In Proceedings of the first international symposium in cryptology in Asia (ASIACRYPT'91) Journal version, entitled ``Instance-Hiding Proof Systems'' co-authored with Beaver, Feigenbaum and Shoup submitted to J. of Cryptology.
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |