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 |