A Note on the Round-Complexity of Concurrent Zero-Knowledge

摘要

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 (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.