1. bookVolume 2022 (2022): Issue 2 (April 2022)
Journal Details
License
Format
Journal
eISSN
2299-0984
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

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

Published Online: 03 Mar 2022
Volume & Issue: Volume 2022 (2022) - Issue 2 (April 2022)
Page range: 517 - 556
Received: 31 Aug 2021
Accepted: 16 Dec 2021
Journal Details
License
Format
Journal
eISSN
2299-0984
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

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 O(N1/c) proof size with a communication complexity of O(D2 ·(N1−2/c+Ns)), where N is the number of gates in the arithmetic circuit representing the predicate and Ns 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.

Keywords

[1] S. Ames, C. Hazay, Y. Ishai, and M. Venkitasubramaniam. Ligero: Lightweight sublinear arguments without a trusted setup. In CCS, pages 2087–2104, 2017.10.1145/3133956.3134104 Search in Google Scholar

[2] C. Baum, A. J. Malozemoff, M. B. Rosen, and P. Scholl. Mac’n’cheese: Zero-knowledge proofs for arithmetic circuits with nested disjunctions. IACR Cryptol. ePrint Arch., 2020:1410, 2020. Search in Google Scholar

[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–410. 2019.10.1145/3335741.3335758 Search in Google Scholar

[4] M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In STOC, pages 1–10, 1988.10.1145/62212.62213 Search in Google Scholar

[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 Search in Google Scholar

[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–128, 2019.10.1007/978-3-030-17653-2_4 Search in Google Scholar

[7] E. Ben-Sasson, A. Chiesa, and N. Spooner. Interactive oracle proofs. In TCC 2016-B Part II, pages 31–60, 2016.10.1007/978-3-662-53644-5_2 Search in Google Scholar

[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–2038, 2020.10.1145/3372297.3417893 Search in Google Scholar

[9] A. J. Blumberg, J. Thaler, V. Vu, and M. Walfish. Verifiable computation using multiple provers. IACR Cryptol. ePrint Arch., 2014:846, 2014. Search in Google Scholar

[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–357, 2016.10.1007/978-3-662-49896-5_12 Search in Google Scholar

[11] J. Bootle, A. Chiesa, and J. Groth. Linear-time arguments with sublinear verification from tensor codes. In Theory of Cryptography Conference, pages 19–46. Springer, 2020.10.1007/978-3-030-64378-2_2 Search in Google Scholar

[12] J. Bootle, A. Chiesa, and S. Liu. Zero-knowledge succinct arguments with a linear-time prover. 2020. Search in Google Scholar

[13] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In IEEE SP, pages 315–334, 2018.10.1109/SP.2018.00020 Search in Google Scholar

[14] R. Canetti. Security and composition of multiparty cryptographic protocols. J. Cryptology, 13(1):143–202, 2000.10.1007/s001459910006 Search in Google Scholar

[15] R. Canetti. Universally composable security: a new paradigm for cryptographic protocols. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 136–145, 2001.10.1109/SFCS.2001.959888 Search in Google Scholar

[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. Search in Google Scholar

[17] R. Cohen and Y. Lindell. Fairness versus guaranteed output delivery in secure multiparty computation. In ASIACRYPT Part II, pages 466–485, 2014.10.1007/978-3-662-45608-8_25 Search in Google Scholar

[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–282, 2017. Search in Google Scholar

[19] I. Damgård, V. Pastro, N. P. Smart, and S. Zakarias. Multiparty computation from somewhat homomorphic encryption. In CRYPTO, pages 643–662, 2012.10.1007/978-3-642-32009-5_38 Search in Google Scholar

[20] Y. Desmedt. Threshold Cryptography, pages 1288–1293. 2011.10.1007/978-1-4419-5906-5_330 Search in Google Scholar

[21] Y. Desmedt, G. D. Crescenzo, and M. Burmester. Multiplicative non-abelian sharing schemes and their application to threshold cryptography. In ASIACRYPT, pages 21–32, 1994.10.1007/BFb0000421 Search in Google Scholar

[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ür Informatik, 2021. Search in Google Scholar

[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–182, 2014.10.1145/2554797.2554815 Search in Google Scholar

[24] J. Eberhardt and S. Tai. Zokrates - scalable privacy-preserving off-chain computations. In IEEE International Conference on Internet of Things (iThings), pages 1084–1091, 2018.10.1109/Cybermatics_2018.2018.00199 Search in Google Scholar

[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/. Search in Google Scholar

[26] A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO, pages 186–194, 1986.10.1007/3-540-47721-7_12 Search in Google Scholar

[27] O. Goldreich. The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press, 2001. Search in Google Scholar

[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–229, 1987.10.1145/28395.28420 Search in Google Scholar

[29] J. Groth. On the size of pairing-based non-interactive arguments. In EUROCRYPT, pages 305–326, 2016.10.1007/978-3-662-49896-5_11 Search in Google Scholar

[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–30, 2007.10.1145/1250790.1250794 Search in Google Scholar

[31] M. Keller, G. L. Mikkelsen, and A. Rupp. Efficient threshold zero-knowledge with applications to user-centric protocols. In ICITS, pages 147–166, 2012.10.1007/978-3-642-32284-6_9 Search in Google Scholar

[32] M. Keller, E. Orsini, and P. Scholl. MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In ACM CCS, pages 830–842, 2016.10.1145/2976749.2978357 Search in Google Scholar

[33] B. King. An efficient implementation of a threshold RSA signature scheme. In ACISP, pages 382–393, 2005.10.1007/11506157_32 Search in Google Scholar

[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. Search in Google Scholar

[35] Y. Lindell. How to simulate it - A tutorial on the simulation proof technique. In Tutorials on the Foundations of Cryptography, pages 277–346. 2017.10.1007/978-3-319-57048-8_6 Search in Google Scholar

[36] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error Correcting Codes. North-Holland Publishing Company, 1978. Search in Google Scholar

[37] B. Parno, J. Howell, C. Gentry, and M. Raykova. Pinocchio: Nearly practical verifiable computation. In IEEE SP, pages 238–252. IEEE, 2013.10.1109/SP.2013.47 Search in Google Scholar

[38] T. P. Pedersen. Distributed provers with applications to undeniable signatures. In EUROCRYPT, pages 221–242, 1991.10.1007/3-540-46416-6_20 Search in Google Scholar

[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 Search in Google Scholar

[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–474, 2014.10.1109/SP.2014.36 Search in Google Scholar

[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–366, 2016.10.1007/978-3-319-39555-5_19 Search in Google Scholar

[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. Search in Google Scholar

[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–1091. IEEE, 2021.10.1109/SP40001.2021.00056 Search in Google Scholar

[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. Search in Google Scholar

[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. Search in Google Scholar

[46] J. Zhang and T. Xie. Virgo: Zero knowledge proofs system without trusted setup. 2019. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo