The Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization


Daniele Micciancio and Scott Yilek


The round-complexity of black-box zero-knowledge has for years been a topic of much interest. Results in this area generally focus on either proving lower bounds in various settings (e.g., Canetti, Kilian, Petrank, and Rosen (SIAM J. Comput. 2003) prove concurrent zero-knowledge (cZK) requires Omega(log n/ log log n) rounds and Barak and Lindell (SIAM J. Comput. 2004) show no constant-round single-session protocol can be zero-knowledge with strict poly-time simulators), or giving upper bounds (e.g., Prabhakaran, Rosen, and Sahai (FOCS 2002) give a cZK protocol with omega(log n) rounds). In this paper we show that though proving upper bounds seems to be quite different from demonstrating lower bounds, underlying both tasks there is a single, simple combinatorial game between two players: a rewinder and a scheduler. We give two theorems relating the success of rewinders in the game to both upper and lower bounds for black-box zero-knowledge in various settings (sequential composition, concurrent composition, etc). Our game and theorems unify the previous results in the area, simplify the task of proving upper and lower bounds, and should be useful in showing future results.


Daniele Micciancio and Scott Yilek.
The Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization.
Proceedings of the Fifth Theory of Cryptography Conference - TCC 2008. LNCS Vol. 4948, pp. 535-552, R. Canetti ed., Springer, 2008.



Conference Version

See Also

TCC 2008