A Note on the Round-Complexity of Concurrent Zero-Knowledge
Alon Rosen
Abstract:
We present a lower bound on the number of rounds required by Concurrent
Zero-Knowledge proofs for languages in NP. It is shown that in the context
of Concurrent Zero-Knowledge, at least eight rounds of interaction are
essential for black-box simulation of non-trivial proof systems (i.e.,
systems for languages that are not in BPP). This improves previously known
lower bounds, and rules out several candidates for constant-round Concurrent
Zero-Knowledge.
In particular, we investigate the Richardson-Kilian protocol~\cite{KR}
(which is the only protocol known to be Concurrent Zero-Knowledge in the
vanilla model), and show that for an apparently natural choice of its main
parameter (which yields a 9-round protocol), the protocol is not likely
to be Concurrent Zero-Knowledge.
Postscript,
gzipped
Postscript.
Back Home