Yao Qi, Raja Das, et al.
ISSTA 2009
We show that any concurrent zero-knowledge protocol for a nontrivial language (i.e., for a language outside BPP), whose security is proven via black-box simulation, must use at least Ω̃(log n) rounds of interaction. This result achieves a substantial improvement over previous lower bounds and is the first bound to rule out the possibility of constant-round concurrent zero-knowledge when proven via black-box simulation. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in NP (which is established via black-box simulation).
Yao Qi, Raja Das, et al.
ISSTA 2009
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Gal Badishi, Idit Keidar, et al.
IEEE TDSC
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989