Abstract
We introduce the problem of Verifiable Relation Sharing (VRS) where a client (prover) wishes to share a vector of secret data items among k servers (the verifiers) while proving in zero-knowledge that the shared data satisfies some properties. This combined task of sharing and proving generalizes notions like verifiable secret sharing and zero-knowledge proofs over secret-shared data. We study VRS from a theoretical perspective and focus on its round complexity.
As our main contribution, we show that every efficiently-computable relation can be realized by a VRS with an optimal round complexity of two rounds where the first round is input-independent (offline round). The protocol achieves full UC-security against an active adversary that is allowed to corrupt any t-subset of the parties that may include the client together with some of the verifiers. For a small (logarithmic) number of parties, we achieve an optimal resiliency threshold of \(t<0.5(k+1)\), and for a large (polynomial) number of parties, we achieve an almost-optimal resiliency threshold of \(t<0.5(k+1)(1-\epsilon )\) for an arbitrarily small constant \(\epsilon >0\). Both protocols can be based on sub-exponentially hard injective one-way functions. If the parties have an access to a collision resistance hash function, we can derive statistical everlasting security, i.e., the protocols are secure against adversaries that are computationally bounded during the protocol execution and become computationally unbounded after the protocol execution.
Previous 2-round solutions achieve smaller resiliency thresholds and weaker security notions regardless of the underlying assumptions. As a special case, our protocols give rise to 2-round offline/online constructions of multi-verifier zero-knowledge proofs (MVZK). Such constructions were previously obtained under the same type of assumptions that are needed for NIZK, i.e., public-key assumptions or random-oracle type assumptions (Abe et al., Asiacrypt 2002; Groth and Ostrovsky, Crypto 2007; Boneh et al., Crypto 2019; Yang, and Wang, Eprint 2022). Our work shows, for the first time, that in the presence of an honest majority these assumptions can be replaced with more conservative “Minicrypt”-type assumptions like injective one-way functions and collision-resistance hash functions. Indeed, our MVZK protocols provide a round-efficient substitute for NIZK in settings where honest-majority is present. Additional applications are also presented.
A full version of this paper appears in [6].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Without an honest majority, a 2-round plain-model MVZK protocol (where in each round both the verifiers and prover can talk simultaneously) implies a 2-step ZK protocol (where the verifier sends a message and gets a response from the prover) which is ruled-out by [36] for non-trivial languages outside \(\text {BPP}\).
- 2.
For technical reasons, the NICOM should satisfy some level of security against selective opening that, by “complexity leveraging”, follows from the assumption that the underlying one-way function (or injective one-way function) cannot be inverted in polynomial-time with more than sub-exponential probability. This seems to be a relatively mild assumption; See Remark 2.
- 3.
The difference between rushing and non-rushing adversary boils down to the scheduling of the messages within a single round of a protocol. A non-rushing adversary must send the messages of the corrupt parties in a given round before receiving the messages of the honest parties in that round, whereas a rushing adversary may delay sending the messages of the corrupt parties until receiving the messages from the honest parties. Thus, the messages of the corrupt parties may depend on the messages of the honest parties in the same round. Our notion of semi-rushing adversary allows the adversary to see all the messages of the honest parties, except for one. For more about this model and its relevance, see the full version [6].
- 4.
Technically, in the UC-framework we allow the environment to output its view and require statistical indistinguishability between the real and ideal experiments.
- 5.
A semi-malicious adversary is allowed to choose its input and randomness but otherwise follows the protocol. Many passively secure protocols (e.g., [12]) actually offer semi-malicious security.
- 6.
Even without homomorphism, computational VSS requires 2 rounds [7] when \(n < 3t\). Moreover, even for such a large resiliency threshold, linear homomorphism is non-trivial to achieve. Specifically, for 2-round VSS, it is unknown how to achieve linear homomorphism without relying on strong primitives such as homomorphic NICOMs. The latter are typically constructed based on “structured” (public-key type) assumptions and are not known to follow from standard NICOMs.
- 7.
In principle, \(n'\) should be taken to be \(\varOmega (1/\epsilon ^2)\). Thus, in order to keep \(n'\) small (e.g., logarithmic in the security parameter), one has to assume that \(\epsilon \) is not too small, e.g., at least \(\varOmega (1/\sqrt{\log \kappa })\). We limit the discussion to a constant \(\epsilon \) only for the sake of simplicity.
- 8.
The circuit that realizes \(\mathcal {G}_{\textsf{zk}}\) depends on the code of the NICOM, consequently, our final construction makes a non-black-box use of the NICOM.
- 9.
We, in fact, consider a weak variant of this sharing in which for a pair of corrupted parties, \((P_i,P_j)\), the share \(f_i(j)\) may be inconsistent with the commitment \(C _{ij}\). Still, it can be shown that \(P_i\) and \(P_j\) cannot lie about their main shares and so this scheme still allows robust reconstruction. For details, refer to the full version of this paper [6].
References
Abe, M., Cramer, R., Fehr, S.: Non-interactive distributed-verifier proofs and proving relations among commitments. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 206–224. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36178-2_13
Ananth, P., Choudhuri, A.R., Goel, A., Jain, A.: Round-optimal secure multiparty computation with honest majority. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part II. LNCS, vol. 10992, pp. 395–424. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_14
Applebaum, B., Kachlon, E., Patra, A.: The resiliency of MPC with low interaction: the benefit of making errors (extended abstract). In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part II. LNCS, vol. 12551, pp. 562–594. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64378-2_20
Applebaum, B., Kachlon, E., Patra, A.: The round complexity of perfect MPC with active security and optimal resiliency. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, 16–19 November 2020, pp. 1277–1284 (2020)
Applebaum, B., Kachlon, E., Patra, A.: Round-optimal honest-majority MPC in minicrypt and with everlasting security. Cryptology ePrint Archive 2021, 346 (2021)
Applebaum, B., Kachlon, E., Patra, A.: Verifiable relation sharing and multi-verifier zero-knowledge in two rounds: trading NIZKs with honest majority. Cryptology ePrint Archive (2022). https://eprint.iacr.org/2022/167
Backes, M., Kate, A., Patra, A.: Computational verifiable secret sharing revisited. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 590–609. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_32
Barak, B., Ong, S.J., Vadhan, S.: Derandomization in cryptography. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 299–315. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_18
Baum, C., Jadoul, R., Orsini, E., Scholl, P., Smart, N.P.: Feta: efficient threshold designated-verifier zero-knowledge proofs. Cryptology ePrint Archive (2022)
Beaver, D.: Efficient multiparty protocols using circuit randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_34
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, Illinois, USA, 2–4 May 1988, pp. 1–10 (1988)
Bitansky, N., Paneth, O.: ZAPs and non-interactive witness indistinguishability from indistinguishability obfuscation. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 401–427. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_16
Blum, M.: Coin flipping by telephone. In: Advances in Cryptology: A Report on CRYPTO 1981, CRYPTO 1981, IEEE Workshop on Communications Security, Santa Barbara, California, USA, 24–26 August 1981, pp. 11–15 (1981)
Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, Illinois, USA, 2–4 May 1988, pp. 103–112 (1988)
Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., Ishai, Y.: Zero-knowledge proofs on secret-shared data via fully linear PCPs. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 67–97. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_3
Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing: improvements and extensions. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 1292–1303 (2016)
Bracha, G.: An o(log n) expected rounds randomized Byzantine generals protocol. J. ACM 34(4), 910–920 (1987)
Brassard, G., Chaum, D., Crépeau, C.: Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37(2), 156–189 (1988)
Burmester, M., Desmedt, Y.: Broadcast interactive proofs. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 81–95. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46416-6_7
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, Las Vegas, Nevada, USA, 14–17 October 2001, pp. 136–145 (2001)
Canetti, R., Kushilevitz, E., Lindell, Y.: On the limitations of universally composable two-party computation without set-up assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 68–86. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_5
Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In: 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21–23 October 1985, pp. 383–395 (1985)
Corrigan-Gibbs, H., Boneh, D.: Prio: private, robust, and scalable computation of aggregate statistics. In: 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2017), pp. 259–282 (2017)
Corrigan-Gibbs, H., Boneh, D., Mazières, D.: Riposte: an anonymous messaging system handling millions of users. In: Proceedings of the 2015 IEEE Symposium on Security and Privacy, pp. 321–338 (2015)
Damgård, I., Ishai, Y., Krøigaard, M., Nielsen, J.B., Smith, A.: Scalable multiparty computation with nearly optimal work and resilience. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 241–261. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_14
Damgård, I., Pedersen, T.P., Pfitzmann, B.: Statistical secrecy and multibit commitments. IEEE Trans. Inf. Theory 44(3), 1143–1151 (1998)
Dwork, C., Naor, M.: Zaps and their applications. SIAM J. Comput. 36(6), 1513–1543 (2007)
Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, Montréal, Québec, Canada, 23–25 May 1994, pp. 554–563 (1994)
Feige, U., Lapidot, D., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29(1), 1–28 (1999)
Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12
Fitzi, M., Franklin, M., Garay, J., Vardhan, S.H.: Towards optimal and efficient perfectly secure message transmission. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 311–322. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70936-7_17
Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: The round complexity of verifiable secret sharing and secure multicast. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 580–589 (2001)
Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: On 2-round secure multiparty computation. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 178–193. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_12
Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, Washigton, USA, 14–17 May 1989, pp. 25–32 (1989)
Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof systems. J. Cryptol. 7(1), 1–32 (1994). https://doi.org/10.1007/BF00195207
Groth, J., Ostrovsky, R.: Cryptography in the multi-string model. J. Cryptol. 27(3), 506–543 (2014). https://doi.org/10.1007/s00145-013-9152-y
Groth, J., Ostrovsky, R., Sahai, A.: New techniques for noninteractive zero-knowledge. J. ACM (JACM) 59(3), 1–35 (2012)
Halevi, S., Micali, S.: Practical and provably-secure commitment schemes from collision-free hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 201–215. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_16
Harnik, D., Ishai, Y., Kushilevitz, E.: How many oblivious transfers are needed for secure multiparty computation? In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 284–302. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_16
Herzberg, A.: Folklore, practice and theory of robust combiners. J. Comput. Secur. 17(2), 159–189 (2009)
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, 11–13 June 2007, pp. 21–30 (2007)
Ishai, Y., Prabhakaran, M., Sahai, A.: Founding cryptography on oblivious transfer – efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_32
Müller-Quade, J., Unruh, D.: Long-term security and universal composability. J. Cryptol. 23(4), 594–671 (2010). https://doi.org/10.1007/978-3-540-70936-7_3
Naor, M.: Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151–158 (1991). https://doi.org/10.1007/BF00196774
Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP using any one-way permutation. J. Cryptol. 11(2), 87–108 (1998). https://doi.org/10.1007/s001459900037
Patra, A., Ravi, D.: On the exact round complexity of secure three-party computation. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part II. LNCS, vol. 10992, pp. 425–458. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_15
Peikert, C., Shiehian, S.: Noninteractive zero knowledge for NP from (Plain) learning with errors. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 89–114. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_4
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, Washington, USA, 14–17 May 1989, pp. 73–85 (1989)
Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pp. 475–484 (2014)
Yang, K., Wang, X.: Non-interactive zero-knowledge proofs to multiple verifiers. Cryptology ePrint Archive (2022)
Yao, A.C.: Theory and applications of trapdoor functions (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3–5 November 1982, pp. 80–91 (1982)
Acknowledgements
B. Applebaum and E. Kachlon are supported by the Israel Science Foundation grant no. 2805/21. A. Patra is supported by DST National Mission on Interdisciplinary Cyber-Physical Systems (NM-CPS) 2020–2025 and SERB MATRICS (Theoretical Sciences) Grant 2020–2023.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 International Association for Cryptologic Research
About this paper
Cite this paper
Applebaum, B., Kachlon, E., Patra, A. (2022). Verifiable Relation Sharing and Multi-verifier Zero-Knowledge in Two Rounds: Trading NIZKs with Honest Majority. In: Dodis, Y., Shrimpton, T. (eds) Advances in Cryptology – CRYPTO 2022. CRYPTO 2022. Lecture Notes in Computer Science, vol 13510. Springer, Cham. https://doi.org/10.1007/978-3-031-15985-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-031-15985-5_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-15984-8
Online ISBN: 978-3-031-15985-5
eBook Packages: Computer ScienceComputer Science (R0)