{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T15:55:41Z","timestamp":1772553341745,"version":"3.50.1"},"reference-count":46,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"2","license":[{"start":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T00:00:00Z","timestamp":1646265600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 Graphene which can be compiled into an efficient DPZK protocol. The (D + 1)-DPZK protocol D-Graphene, with D provers and one verifier, admits<jats:italic>O<\/jats:italic>(<jats:italic>N<\/jats:italic><jats:sup>1<\/jats:sup><jats:italic><jats:sup>\/c<\/jats:sup><\/jats:italic>) proof size with a communication complexity of<jats:italic>O<\/jats:italic>(D<jats:sup>2<\/jats:sup>\u00b7(<jats:italic>N<\/jats:italic><jats:sup>1\u22122<\/jats:sup><jats:italic><jats:sup>\/c<\/jats:sup><\/jats:italic>+<jats:italic>N<jats:sub>s<\/jats:sub><\/jats:italic>)), where<jats:italic>N<\/jats:italic>is the number of gates in the arithmetic circuit representing the predicate and<jats:italic>N<jats:sub>s<\/jats:sub><\/jats:italic>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.<\/jats:p>","DOI":"10.2478\/popets-2022-0055","type":"journal-article","created":{"date-parts":[[2022,3,5]],"date-time":"2022-03-05T04:38:28Z","timestamp":1646455108000},"page":"517-556","source":"Crossref","is-referenced-by-count":9,"title":["How to prove any NP statement jointly? Efficient Distributed-prover Zero-Knowledge Protocols"],"prefix":"10.56553","volume":"2022","author":[{"given":"Pankaj","family":"Dayama","sequence":"first","affiliation":[{"name":"IBM Research, IBM"}]},{"given":"Arpita","family":"Patra","sequence":"additional","affiliation":[{"name":"Indian Institute of Science Bangalore"}]},{"given":"Protik","family":"Paul","sequence":"additional","affiliation":[{"name":"Indian Institute of Science Bangalore"}]},{"given":"Nitin","family":"Singh","sequence":"additional","affiliation":[{"name":"IBM Research"}]},{"given":"Dhinakaran","family":"Vinayagamurthy","sequence":"additional","affiliation":[{"name":"IBM Research"}]}],"member":"35752","published-online":{"date-parts":[[2022,3,3]]},"reference":[{"key":"2022060209294772767_j_popets-2022-0055_ref_001","doi-asserted-by":"crossref","unstructured":"[1] S. Ames, C. Hazay, Y. Ishai, and M. Venkitasubramaniam. Ligero: Lightweight sublinear arguments without a trusted setup. In CCS, pages 2087\u20132104, 2017.10.1145\/3133956.3134104","DOI":"10.1145\/3133956.3134104"},{"key":"2022060209294772767_j_popets-2022-0055_ref_002","unstructured":"[2] C. Baum, A. J. Malozemoff, M. B. Rosen, and P. Scholl. Mac\u2019n\u2019cheese: Zero-knowledge proofs for arithmetic circuits with nested disjunctions. IACR Cryptol. ePrint Arch., 2020:1410, 2020."},{"key":"2022060209294772767_j_popets-2022-0055_ref_003","doi-asserted-by":"crossref","unstructured":"[3] M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pages 373\u2013410. 2019.10.1145\/3335741.3335758","DOI":"10.1145\/3335741.3335758"},{"key":"2022060209294772767_j_popets-2022-0055_ref_004","doi-asserted-by":"crossref","unstructured":"[4] M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In STOC, pages 1\u201310, 1988.10.1145\/62212.62213","DOI":"10.1145\/62212.62213"},{"key":"2022060209294772767_j_popets-2022-0055_ref_005","doi-asserted-by":"crossref","unstructured":"[5] E. Ben-Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza. Zerocash: Decentralized anonymous payments from bitcoin. Cryptology ePrint Archive, Report 2014\/349, 2014.10.1109\/SP.2014.36","DOI":"10.1109\/SP.2014.36"},{"key":"2022060209294772767_j_popets-2022-0055_ref_006","doi-asserted-by":"crossref","unstructured":"[6] E. Ben-Sasson, A. Chiesa, M. Riabzev, N. Spooner, M. Virza, and N. P. Ward. Aurora: Transparent succinct arguments for R1CS. In EUROCRYPT Part I, pages 103\u2013128, 2019.10.1007\/978-3-030-17653-2_4","DOI":"10.1007\/978-3-030-17653-2_4"},{"key":"2022060209294772767_j_popets-2022-0055_ref_007","doi-asserted-by":"crossref","unstructured":"[7] E. Ben-Sasson, A. Chiesa, and N. Spooner. Interactive oracle proofs. In TCC 2016-B Part II, pages 31\u201360, 2016.10.1007\/978-3-662-53644-5_2","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"2022060209294772767_j_popets-2022-0055_ref_008","doi-asserted-by":"crossref","unstructured":"[8] R. Bhadauria, Z. Fang, C. Hazay, M. Venkitasubramaniam, T. Xie, and Y. Zhang. Ligero++: A new optimized sublinear iop. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 2025\u20132038, 2020.10.1145\/3372297.3417893","DOI":"10.1145\/3372297.3417893"},{"key":"2022060209294772767_j_popets-2022-0055_ref_009","unstructured":"[9] A. J. Blumberg, J. Thaler, V. Vu, and M. Walfish. Verifiable computation using multiple provers. IACR Cryptol. ePrint Arch., 2014:846, 2014."},{"key":"2022060209294772767_j_popets-2022-0055_ref_010","doi-asserted-by":"crossref","unstructured":"[10] J. Bootle, A. Cerulli, P. Chaidos, J. Groth, and C. Petit. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In EUROCRYPT Part II, pages 327\u2013357, 2016.10.1007\/978-3-662-49896-5_12","DOI":"10.1007\/978-3-662-49896-5_12"},{"key":"2022060209294772767_j_popets-2022-0055_ref_011","doi-asserted-by":"crossref","unstructured":"[11] J. Bootle, A. Chiesa, and J. Groth. Linear-time arguments with sublinear verification from tensor codes. In Theory of Cryptography Conference, pages 19\u201346. Springer, 2020.10.1007\/978-3-030-64378-2_2","DOI":"10.1007\/978-3-030-64378-2_2"},{"key":"2022060209294772767_j_popets-2022-0055_ref_012","unstructured":"[12] J. Bootle, A. Chiesa, and S. Liu. Zero-knowledge succinct arguments with a linear-time prover. 2020."},{"key":"2022060209294772767_j_popets-2022-0055_ref_013","doi-asserted-by":"crossref","unstructured":"[13] B. B\u00fcnz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In IEEE SP, pages 315\u2013334, 2018.10.1109\/SP.2018.00020","DOI":"10.1109\/SP.2018.00020"},{"key":"2022060209294772767_j_popets-2022-0055_ref_014","doi-asserted-by":"crossref","unstructured":"[14] R. Canetti. Security and composition of multiparty cryptographic protocols. J. Cryptology, 13(1):143\u2013202, 2000.10.1007\/s001459910006","DOI":"10.1007\/s001459910006"},{"key":"2022060209294772767_j_popets-2022-0055_ref_015","doi-asserted-by":"crossref","unstructured":"[15] R. Canetti. Universally composable security: a new paradigm for cryptographic protocols. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 136\u2013145, 2001.10.1109\/SFCS.2001.959888","DOI":"10.1109\/SFCS.2001.959888"},{"key":"2022060209294772767_j_popets-2022-0055_ref_016","unstructured":"[16] A. Chiesa, Y. Hu, M. Maller, P. Mishra, N. Vesely, and N. P. Ward. Marlin: Preprocessing zksnarks with universal and updatable SRS. IACR Cryptology ePrint Archive, 2019:1047, 2019."},{"key":"2022060209294772767_j_popets-2022-0055_ref_017","doi-asserted-by":"crossref","unstructured":"[17] R. Cohen and Y. Lindell. Fairness versus guaranteed output delivery in secure multiparty computation. In ASIACRYPT Part II, pages 466\u2013485, 2014.10.1007\/978-3-662-45608-8_25","DOI":"10.1007\/978-3-662-45608-8_25"},{"key":"2022060209294772767_j_popets-2022-0055_ref_018","unstructured":"[18] H. Corrigan-Gibbs and D. Boneh. Prio: Private, robust, and scalable computation of aggregate statistics. In 14th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 17), pages 259\u2013282, 2017."},{"key":"2022060209294772767_j_popets-2022-0055_ref_019","doi-asserted-by":"crossref","unstructured":"[19] I. Damg\u00e5rd, V. Pastro, N. P. Smart, and S. Zakarias. Multiparty computation from somewhat homomorphic encryption. In CRYPTO, pages 643\u2013662, 2012.10.1007\/978-3-642-32009-5_38","DOI":"10.1007\/978-3-642-32009-5_38"},{"key":"2022060209294772767_j_popets-2022-0055_ref_020","doi-asserted-by":"crossref","unstructured":"[20] Y. Desmedt. Threshold Cryptography, pages 1288\u20131293. 2011.10.1007\/978-1-4419-5906-5_330","DOI":"10.1007\/978-1-4419-5906-5_330"},{"key":"2022060209294772767_j_popets-2022-0055_ref_021","doi-asserted-by":"crossref","unstructured":"[21] Y. Desmedt, G. D. Crescenzo, and M. Burmester. Multiplicative non-abelian sharing schemes and their application to threshold cryptography. In ASIACRYPT, pages 21\u201332, 1994.10.1007\/BFb0000421","DOI":"10.1007\/BFb0000421"},{"key":"2022060209294772767_j_popets-2022-0055_ref_022","doi-asserted-by":"crossref","unstructured":"[22] S. Dittmer, Y. Ishai, and R. Ostrovsky. Line-point zero knowledge and its applications. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2021.","DOI":"10.1145\/3548606.3559385"},{"key":"2022060209294772767_j_popets-2022-0055_ref_023","doi-asserted-by":"crossref","unstructured":"[23] E. Druk and Y. Ishai. Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 169\u2013182, 2014.10.1145\/2554797.2554815","DOI":"10.1145\/2554797.2554815"},{"key":"2022060209294772767_j_popets-2022-0055_ref_024","doi-asserted-by":"crossref","unstructured":"[24] J. Eberhardt and S. Tai. Zokrates - scalable privacy-preserving off-chain computations. In IEEE International Conference on Internet of Things (iThings), pages 1084\u20131091, 2018.10.1109\/Cybermatics_2018.2018.00199","DOI":"10.1109\/Cybermatics_2018.2018.00199"},{"key":"2022060209294772767_j_popets-2022-0055_ref_025","unstructured":"[25] S. Englehardt. Privacy-preserving mozilla telemetry with prio. https:\/\/blog.mozilla.org\/security\/2019\/06\/06\/next-steps-in-privacy-preserving-telemetry-with-prio\/."},{"key":"2022060209294772767_j_popets-2022-0055_ref_026","doi-asserted-by":"crossref","unstructured":"[26] A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO, pages 186\u2013194, 1986.10.1007\/3-540-47721-7_12","DOI":"10.1007\/3-540-47721-7_12"},{"key":"2022060209294772767_j_popets-2022-0055_ref_027","unstructured":"[27] O. Goldreich. The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press, 2001."},{"key":"2022060209294772767_j_popets-2022-0055_ref_028","doi-asserted-by":"crossref","unstructured":"[28] O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In STOC, pages 218\u2013229, 1987.10.1145\/28395.28420","DOI":"10.1145\/28395.28420"},{"key":"2022060209294772767_j_popets-2022-0055_ref_029","doi-asserted-by":"crossref","unstructured":"[29] J. Groth. On the size of pairing-based non-interactive arguments. In EUROCRYPT, pages 305\u2013326, 2016.10.1007\/978-3-662-49896-5_11","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"2022060209294772767_j_popets-2022-0055_ref_030","doi-asserted-by":"crossref","unstructured":"[30] Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai. Zero-knowledge from secure multiparty computation. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 21\u201330, 2007.10.1145\/1250790.1250794","DOI":"10.1145\/1250790.1250794"},{"key":"2022060209294772767_j_popets-2022-0055_ref_031","doi-asserted-by":"crossref","unstructured":"[31] M. Keller, G. L. Mikkelsen, and A. Rupp. Efficient threshold zero-knowledge with applications to user-centric protocols. In ICITS, pages 147\u2013166, 2012.10.1007\/978-3-642-32284-6_9","DOI":"10.1007\/978-3-642-32284-6_9"},{"key":"2022060209294772767_j_popets-2022-0055_ref_032","doi-asserted-by":"crossref","unstructured":"[32] M. Keller, E. Orsini, and P. Scholl. MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In ACM CCS, pages 830\u2013842, 2016.10.1145\/2976749.2978357","DOI":"10.1145\/2976749.2978357"},{"key":"2022060209294772767_j_popets-2022-0055_ref_033","doi-asserted-by":"crossref","unstructured":"[33] B. King. An efficient implementation of a threshold RSA signature scheme. In ACISP, pages 382\u2013393, 2005.10.1007\/11506157_32","DOI":"10.1007\/11506157_32"},{"key":"2022060209294772767_j_popets-2022-0055_ref_034","unstructured":"[34] B. Libert, S. Ramanna, and M. Yung. Functional commitment schemes: From polynomial commitments to pairingbased accumulators from simple assumptions. In 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), 2016."},{"key":"2022060209294772767_j_popets-2022-0055_ref_035","doi-asserted-by":"crossref","unstructured":"[35] Y. Lindell. How to simulate it - A tutorial on the simulation proof technique. In Tutorials on the Foundations of Cryptography, pages 277\u2013346. 2017.10.1007\/978-3-319-57048-8_6","DOI":"10.1007\/978-3-319-57048-8_6"},{"key":"2022060209294772767_j_popets-2022-0055_ref_036","unstructured":"[36] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error Correcting Codes. North-Holland Publishing Company, 1978."},{"key":"2022060209294772767_j_popets-2022-0055_ref_037","doi-asserted-by":"crossref","unstructured":"[37] B. Parno, J. Howell, C. Gentry, and M. Raykova. Pinocchio: Nearly practical verifiable computation. In IEEE SP, pages 238\u2013252. IEEE, 2013.10.1109\/SP.2013.47","DOI":"10.1109\/SP.2013.47"},{"key":"2022060209294772767_j_popets-2022-0055_ref_038","doi-asserted-by":"crossref","unstructured":"[38] T. P. Pedersen. Distributed provers with applications to undeniable signatures. In EUROCRYPT, pages 221\u2013242, 1991.10.1007\/3-540-46416-6_20","DOI":"10.1007\/3-540-46416-6_20"},{"key":"2022060209294772767_j_popets-2022-0055_ref_039","doi-asserted-by":"crossref","unstructured":"[39] T. P. Pedersen. Distributed provers and verifiable secret sharing based on the discrete logarithm problem. DAIMI Report Series, 21(388), 1992. PhD Thesis.10.7146\/dpb.v21i388.6621","DOI":"10.7146\/dpb.v21i388.6621"},{"key":"2022060209294772767_j_popets-2022-0055_ref_040","doi-asserted-by":"crossref","unstructured":"[40] E. B. Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza. Zerocash: Decentralized anonymous payments from bitcoin. In IEEE SP, pages 459\u2013474, 2014.10.1109\/SP.2014.36","DOI":"10.1109\/SP.2014.36"},{"key":"2022060209294772767_j_popets-2022-0055_ref_041","doi-asserted-by":"crossref","unstructured":"[41] B. Schoenmakers, M. Veeningen, and N. de Vreede. Trinocchio: Privacy-preserving outsourcing by distributed verifiable computation. In M. Manulis, A.-R. Sadeghi, and S. Schneider, editors, ACNS, pages 346\u2013366, 2016.10.1007\/978-3-319-39555-5_19","DOI":"10.1007\/978-3-319-39555-5_19"},{"key":"2022060209294772767_j_popets-2022-0055_ref_042","unstructured":"[42] S. Setty. Spartan: Efficient and general-purpose zksnarks without trusted setup. Cryptology ePrint Archive, Report 2019\/550, 2019. https:\/\/eprint.iacr.org\/2019\/550."},{"key":"2022060209294772767_j_popets-2022-0055_ref_043","doi-asserted-by":"crossref","unstructured":"[43] C. Weng, K. Yang, J. Katz, and X. Wang. Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits. In 2021 IEEE Symposium on Security and Privacy (SP), pages 1074\u20131091. IEEE, 2021.10.1109\/SP40001.2021.00056","DOI":"10.1109\/SP40001.2021.00056"},{"key":"2022060209294772767_j_popets-2022-0055_ref_044","unstructured":"[44] H. Wu, W. Zheng, A. Chiesa, R. A. Popa, and I. Stoica. DIZK: A distributed zero knowledge proof system. IACR Cryptology ePrint Archive, 2018:691, 2018."},{"key":"2022060209294772767_j_popets-2022-0055_ref_045","doi-asserted-by":"crossref","unstructured":"[45] K. Yang, P. Sarkar, C. Weng, and X. Wang. Quicksilver: Efficient and affordable zero-knowledge proofs for circuits and polynomials over any field. IACR Cryptol. ePrint Arch., 2021:76, 2021.","DOI":"10.1145\/3460120.3484556"},{"key":"2022060209294772767_j_popets-2022-0055_ref_046","unstructured":"[46] J. Zhang and T. Xie. Virgo: Zero knowledge proofs system without trusted setup. 2019."}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/popets-2022-0055","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T12:16:31Z","timestamp":1674908191000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2022\/popets-2022-0055.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,3]]},"references-count":46,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,3,3]]},"published-print":{"date-parts":[[2022,4,1]]}},"alternative-id":["10.2478\/popets-2022-0055"],"URL":"https:\/\/doi.org\/10.2478\/popets-2022-0055","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,3]]}}}