Abstract
Secure multi-party computation (MPC) allows a set of n players to securely compute an agreed function of their inputs, even when up to t players are under the control of an adversary. Known asynchronous MPC protocols require communication of at least Ω(n 3) (with cryptographic security), respectively Ω(n 4) (with information-theoretic security, but with error probability and non-optimal resilience) field elements per multiplication.
We present an asynchronous MPC protocol communicating \(\mathcal{O}(n^3)\) field elements per multiplication. Our protocol provides perfect security against an active, adaptive adversary corrupting t < n/4 players, which is optimal. This communication complexity is to be compared with the most efficient previously known protocol for the same model, which requires Ω(n 5) field elements of communication (i.e., Ω(n 3) broadcasts). Our protocol is as efficient as the most efficient perfectly secure protocol for the synchronous model and the most efficient asynchronous protocol with cryptographic security.
Furthermore, we enhance our MPC protocol for a hybrid model. In the fully asynchronous model, up to t honest players might not be able to provide their input in the computation. In the hybrid model, all players are able to provide their input, given that the very first round of communication is synchronous. We provide an MPC protocol with communicating \(\mathcal{O}(n^3)\) field elements per multiplication, where all players can provide their input if the first communication round turns out to be synchronous, and all but at most t players can provide their input if the communication is fully asynchronous. The protocol does not need to know whether or not the first communication round is synchronous, thus combining the advantages of the synchronous world and the asynchronous world. The proposed MPC protocol is the first protocol with this property.
This work was partially supported by the Zurich Information Security Center. It represents the views of the authors.
Chapter PDF
Similar content being viewed by others
References
Ben-Or, M., Canetti, R., Goldreich, O.: Asynchronous secure computation. In: Proc. 25th STOC, pp. 52–61 (1993)
Beaver, D.: Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. Journal of Cryptology, 75–122 (1991)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proc. 20th STOC, pp. 1–10 (1988)
Beerliova-Trubiniova, Z., Hirt, M.: Efficient multi-party computation with dispute control. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 305–328. Springer, Heidelberg (2006)
Ben-Or, M., Kelmer, B., Rabin, T.: Asynchronous secure computations with optimal resilience (extended abstract). In: Proc. 13th PODC, pp. 183–192 (1994)
Bracha, G.: An asynchronous \(\lfloor(n - 1)/3\rfloor\)-resilient consensus protocol. In: Proc. 3rd PODC, pp. 154–162 (1984)
Canetti, R.: Studies in Secure Multiparty Computation and Applications. PhD thesis, Weizmann Institute, Israel (June 1995)
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (extended abstract). In: Proc. 20th STOC, pp. 11–19 (1988)
Chaum, D., Damgård, I., van de Graaf, J.: Multiparty computations ensuring privacy of each party’s input and correctness of the result. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 87–119. Springer, Heidelberg (1988)
Damgård, I., Nielsen, J.B.: Robust multiparty computation with linear communication complexity. In: CRYPTO 2007. LNCS, vol. 4622, Springer, Heidelberg (2007)
Galil, Z., Haber, S., Yung, M.: Cryptographic computation: Secure fault-tolerant protocols and the public-key model. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 135–155. Springer, Heidelberg (1988)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game — a completeness theorem for protocols with honest majority. In: Proc. 19th STOC, pp. 218–229 (1987)
Hirt, M., Maurer, U., Przydatek, B.: Efficient secure multi-party computation. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 143–161. Springer, Heidelberg (2000)
Hirt, M., Nielsen, J.B.: Robust multiparty computation with linear communication complexity. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 463–482. Springer, Heidelberg (2006)
Hirt, M., Nielsen, J.B., Przydatek, B.: Cryptographic asynchronous multi-party computation with optimal resilience. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 322–340. Springer, Heidelberg (2005)
Prabhu, B., Srinathan, K., Rangan, C.P.: Asynchronous unconditionally secure computation: An efficiency improvement. In: Menezes, A.J., Sarkar, P. (eds.) INDOCRYPT 2002. LNCS, vol. 2551, Springer, Heidelberg (2002)
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority. In: Proc. 21st STOC, pp. 73–85 (1989)
Shamir, A.: How to share a secret. Communications of the ACM 22, 612–613 (1979)
Srinathan, K., Rangan, C.P.: Efficient asynchronous secure multiparty distributed computation. In: Roy, B., Okamoto, E. (eds.) INDOCRYPT 2000. LNCS, vol. 1977, Springer, Heidelberg (2000)
Yao, A.C.: Protocols for secure computations. In: Proc. 23rd FOCS, pp. 160–164 (1982)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beerliová-Trubíniová, Z., Hirt, M. (2007). Simple and Efficient Perfectly-Secure Asynchronous MPC. In: Kurosawa, K. (eds) Advances in Cryptology – ASIACRYPT 2007. ASIACRYPT 2007. Lecture Notes in Computer Science, vol 4833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-76900-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-76900-2_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-76899-9
Online ISBN: 978-3-540-76900-2
eBook Packages: Computer ScienceComputer Science (R0)