Abstract
We study the following two related questions:
-
What are the minimal computational resources required for general secure multiparty computation in the presence of an honest majority?
-
What are the minimal resources required for two-party primitives such as zero-knowledge proofs and general secure two-party computation?
We obtain a nearly tight answer to the first question by presenting a perfectly secure protocol which allows n players to evaluate an arithmetic circuit of size s by performing a total of \(\mathcal{O}(s\log s\log^2 n)\) arithmetic operations, plus an additive term which depends (polynomially) on n and the circuit depth, but only logarithmically on s. Thus, for typical large-scale computations whose circuit width is much bigger than their depth and the number of players, the amortized overhead is just polylogarithmic in n and s. The protocol provides perfect security with guaranteed output delivery in the presence of an active, adaptive adversary corrupting a (1/3 − ε) fraction of the players, for an arbitrary constant ε> 0 and sufficiently large n. The best previous protocols in this setting could only offer computational security with a computational overhead of poly(k,logn,logs), where k is a computational security parameter, or perfect security with a computational overhead of \(\mathcal{O}(n\log n)\).
We then apply the above result towards making progress on the second question. Concretely, under standard cryptographic assumptions, we obtain zero-knowledge proofs for circuit satisfiability with 2− k soundness error in which the amortized computational overhead per gate is only polylogarithmic in k, improving over the ω(k) overhead of the best previous protocols. Under stronger cryptographic assumptions, we obtain similar results for general secure two-party computation.
Chapter PDF
Similar content being viewed by others
Keywords
- Computational Overhead
- Oblivious Transfer
- Arithmetic Circuit
- Secure Multiparty Computation
- Adaptive Adversary
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 595–618. Springer, Heidelberg (2009)
Beerliová-Trubíniová, Z., Hirt, M.: Perfectly-secure MPC with linear communication complexity. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 213–230. Springer, Heidelberg (2008)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: STOC, pp. 1–10. ACM, New York (1988)
Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Short pcps verifiable in polylogarithmic time. In: IEEE Conference on Computational Complexity, pp. 120–134. IEEE Computer Society, Los Alamitos (2005)
Benes, V.E.: Optimal rearrangable multistage connecting networks. The Bell System Technical Journal 43, 1641–1656 (1964)
Bracha, G.: An O(log n) expected rounds randomized byzantine generals protocol. J. ACM 34(4), 910–920 (1987)
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: FOCS 2001: Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, Washington, DC, USA, pp. 136–145. IEEE Computer Society, Los Alamitos (2001)
Chaum, D., Crépeau, C., Damgard, I.: Multiparty unconditionally secure protocols. In: STOC 1988: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 11–19. ACM, New York (1988)
Chen, H., Cramer, R.: Algebraic geometric secret sharing schemes and secure multi-party computations over small fields. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 521–536. Springer, Heidelberg (2006)
Cramer, R., Damgård, I., Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–299. Springer, Heidelberg (2001)
Damgård, I., Ishai, Y.: Scalable secure multiparty computation. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 501–520. Springer, Heidelberg (2006)
Damgård, I., Ishai, Y., Krøigaard, M.: Perfectly secure multiparty computation and the computational overhead of cryptography. Cryptology ePrint archive, report 2010/131 (2010), http://eprint.iacr.org/
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)
Franklin, M.K., Yung, M.: Communication complexity of secure computation (extended abstract). In: STOC, pp. 699–710. ACM, New York (1992)
Gennaro, R., Rabin, M.O., Rabin, T.: Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In: PODC 1998: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, pp. 101–111. ACM, New York (1998)
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 1909: Proceedings of the 41st annual ACM symposium on Theory of computing, pp. 169–178. ACM, New York (2009)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC, pp. 218–229. ACM, New York (1987)
Hirt, M., Maurer, U.M.: Player simulation and general adversary structures in perfect multiparty computation. J. Cryptology 13(1), 31–60 (2000)
Hirt, M., Maurer, U.M., Przydatek, B.: Efficient secure multi-party computation. In: ASIACRYPT 2000: Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security, London, UK, pp. 143–161. Springer, Heidelberg (2000)
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 21–30. ACM, New York (2007)
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing, pp. 433–442. ACM, New York (2008)
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)
Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: STOC 1992: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pp. 723–732. ACM, New York (1992)
Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006, Part II. LNCS, vol. 4052, pp. 144–155. Springer, Heidelberg (2006)
Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253–1298 (2000)
Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 145–166. Springer, Heidelberg (2006)
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority. In: STOC 1989: Proceedings of the twenty-first annual ACM symposium on Theory of computing, pp. 73–85. ACM, New York (1989)
Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)
Waksman, A.: A permutation network. J. ACM 15(1), 159–163 (1968)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damgård, I., Ishai, Y., Krøigaard, M. (2010). Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography. In: Gilbert, H. (eds) Advances in Cryptology – EUROCRYPT 2010. EUROCRYPT 2010. Lecture Notes in Computer Science, vol 6110. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13190-5_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-13190-5_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13189-9
Online ISBN: 978-3-642-13190-5
eBook Packages: Computer ScienceComputer Science (R0)