Cryptology ePrint Archive: Report 2014/633

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

Ran Canetti and Abhishek Jain and Omer Paneth

Abstract: 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].

Category / Keywords: cryptographic protocols /

Original Publication (in the same form): IACR-CRYPTO-2014

Date: received 17 Aug 2014

Contact author: abhishek at csail mit edu

Available format(s): PDF | BibTeX Citation

Version: 20140821:010657 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]