**
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 |