Paper 2021/1599

How to prove any NP statement jointly? Efficient Distributed-prover Zero-Knowledge Protocols

Pankaj Dayama, IBM IRL
Arpita Patra, Indian Institute of Science Bangalore
Protik Paul, Indian Institute of Science Bangalore
Nitin Singh, IBM IRL
Dhinakaran Vinayagamurthy, IBM IRL

Traditional zero-knowledge protocols have been studied and optimized for the setting where a single prover holds the complete witness and tries to convince a verifier about a predicate on the witness, without revealing any additional information to the verifier. In this work, we study the notion of distributed-prover zero knowledge (DPZK) for arbitrary predicates where the witness is shared among multiple mutually distrusting provers and they want to convince a verifier that their shares together satisfy the predicate. We make the following contributions to the notion of distributed proof generation: (i) we propose a new MPC-style security definition to capture the adversarial settings possible for different collusion models between the provers and the verifier, (ii) we discuss new efficiency parameters for distributed proof generation such as the number of rounds of interaction and the amount of communication among the provers, and (iii) we propose a compiler that realizes distributed proof generation from the zero-knowledge protocols in the Interactive Oracle Proofs (IOP) paradigm. Our compiler can be used to obtain DPZK from arbitrary IOP protocols, but the concrete efficiency overheads are substantial in general. To this end, we contribute (iv) a new zero-knowledge IOP $\textsf{Graphene}$ which can be compiled into an efficient DPZK protocol. The $(\mathsf{D} + 1)$-DPZK protocol $\text{D-Graphene}$, with $\mathsf{D}$ provers and one verifier, admits $O(N^{1/c})$ proof size with a communication complexity of $O(\mathsf{D}^2\cdot (N^{1-2/c} + N_s))$, where $N$ is the number of gates in the arithmetic circuit representing the predicate and $N_s$ is the number of wires that depends on inputs from two or more parties. Significantly, only the distributed proof generation in $\text{D-Graphene}$ requires interaction among the provers. $\text{D-Graphene}$ compares favourably with the DPZK protocols obtained from the state-of-art zero-knowledge protocols, even those not modelled as IOPs.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Privacy Enhancing Technologies Symposium (PETS) 2022
Zero-Knowledge Multi-party Computation Distributed Prover
Contact author(s)
pankajdayama @ in ibm com
arpita @ iisc ac in
protikpaul @ iisc ac in
nitisin1 @ in ibm com
dvinaya1 @ in ibm com
2022-07-26: last of 2 revisions
2021-12-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pankaj Dayama and Arpita Patra and Protik Paul and Nitin Singh and Dhinakaran Vinayagamurthy},
      title = {How to prove any NP statement jointly? Efficient Distributed-prover Zero-Knowledge Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1599},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.