Concurrent Zero-Knowledge with Logarithmic Round
Compexity
Manoj Prabhakaran, Alon Rosen and Amit Sahai
Abstract:
We show that every language in NP has a (black-box) concurrent zero-knowledge
proof system using ~O}(log n) rounds of interaction. The number of rounds
in our protocol is optimal, in the sense that any language outside BPP
requires at least ~Omega(log n) rounds of interaction in order to be proved
in black-box concurrent zero-knowledge. The zero-knowledge property
of our main protocol is proved under the assumption that there exists a
collection of claw-free functions. Assuming only the existence of one-way
functions, we show the existence of ~O(log n)-round concurrent zero-knowledge
arguments for all languages in NP.
Postscript,
gzipped
Postscript.
Back Home