Rafail Ostrovsky - Publications

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