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

Abstract

Traditional zero-knowledge protocols have been studied and optimized for the setting where a sin- gle prover holds the complete witness and tries to con- vince a verifier about a predicate on the witness, with- out revealing any additional information to the veri- fier. 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 veri- fier that their shares together satisfy the predicate. We make the following contributions to the notion of dis- tributed proof generation: (i) we propose a new MPC- style security definition to capture the adversarial set- tings 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 pro- pose a compiler that realizes distributed proof gener- ation from the zero-knowledge protocols in the Interac- tive 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 Graphene which can be compiled into an efficient DPZK protocol. The (D + 1)-DPZK proto- col D-Graphene, with D provers and one verifier, admits $ O(N1/^c) $ proof size with a communication complexity of $ O(D2·(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 D-Graphene requires interaction among the provers. D-Graphene compares favourably with the DPZK protocols obtained from the state-of-art zero- knowledge protocols, even those not modelled as IOPs.