Collaborative CP-NIZKs: modular, composable proofs for distributed secrets

Abstract Non-interactive zero-knowledge (NIZK) proofs of knowledge have proven to be highly relevant for securely realizing a wide array of applications that rely on both privacy and correctness . They enable a prover to convince any party of the correctness of a public statement for a secret witness . However, most NIZKs do not natively support proving knowledge of a secret witness that is distributed over multiple provers. Previously, collaborative proofs [54] have been proposed to overcome this limitation. We investigate the notion of composability in this setting, following the Commit-and-Prove design of LegoSNARK [19]. Composability allows users to combine different, specialized NIZKs (e.g., one for arithmetic circuits, one for boolean circuits, and one for range proofs) with the aim of reducing the proof generation time. Moreover, it opens the door to efficient realizations of many applications in the collaborative setting such as mutually exclusive prover groups, combining collaborative and single-party proofs and efficiently implementing publicly auditable secure multiparty computing (PA-MPC). We present the first, general definition for collaborative commitand- prove NIZK (CP-NIZK) proofs of knowledge and construct MPC protocols to enable their realization. We implement our protocols for two commonly used NIZKs, Groth16 and Bulletproofs, and evaluate their practicality in a variety of computational settings. Our findings indicate that composability adds only minor overhead, especially for large circuits. We also evaluated our construction in two application settings, one of which shows 18– $$55\times $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>55</mml:mn> <mml:mo>×</mml:mo> </mml:mrow> </mml:math> runtime reduction when compared to prior works while requiring only a fraction ( $$0.2\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>0.2</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> ) of the communication.