Paper 2014/633

Client-Server Concurrent Zero Knowledge with Constant Rounds and Guaranteed Complexity

Ran Canetti, Abhishek Jain, and Omer Paneth


The traditional setting for concurrent zero knowledge considers a server that proves a statement in zero-knowledge to multiple clients in multiple concurrent sessions, where the server's actions in a session are independent of all other sessions. Persiano and Visconti [ICALP 05] show how keeping a limited amount of global state across sessions allows the server to significantly reduce the overall complexity while retaining the ability to interact concurrently with an unbounded number of clients. Specifically, they show a protocol that has only slightly super-constant number of rounds; however the communication complexity in each session of their protocol depends on the number of other sessions and has no a priori bound. This has the drawback that the client has no way to know in advance the amount of resources required for completing a session of the protocol up to the moment where the session is completed. We show a protocol that does not have this drawback. Specifically, in our protocol the client obtains a bound on the communication complexity of each session at the start of the session. Additionally the protocol is constant-rounds. Our protocol is fully concurrent, and assumes only collision-resistant hash functions. The proof requires considerably different techniques than those of Persiano and Visconti. Our main technical tool is an adaptation of the "committed-simulator" technique of Deng et. al [FOCS 09].

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in CRYPTO 2014
Contact author(s)
abhishek @ csail mit edu
2014-08-21: received
Short URL
Creative Commons Attribution


      author = {Ran Canetti and Abhishek Jain and Omer Paneth},
      title = {Client-Server Concurrent Zero Knowledge with Constant Rounds and Guaranteed Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2014/633},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.