Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity.

Abstract

We consider the problem of constructing Concurrent Zero Knowledge Proofs [6], in which the fascinating and useful "zero knowledge" property is guaranteed even in situations where multiple concurrent proof sessions are executed with many colluding dishonest verifiers. Canetti et al. [3] show that blackbox concurrent zero knowledge proofs for non-trivial languages require #4 k) rounds where k is the security parameter. Till now the best known upper bound on the number of rounds for NP languages was #(log k), due to Kilian and Petrank [16]. We establish an upper bound of #(log k) on the number of rounds for NP languages, thereby closing the gap between the upper and lower bounds, up to a #(log log k) factor.