Abstract
Secure multiparty computation (MPC) allows a set of n parties to securely compute a function of their private inputs against an adversary corrupting up to t parties. Over the previous decade, the communication complexity of synchronous MPC protocols could be improved to \(\mathcal{O}(n)\) per multiplication, for various settings. However, designing an asynchronous MPC (AMPC) protocol with linear communication complexity was not achieved so far. We solve this open problem by presenting two AMPC protocols with the corruption threshold t < n / 4. Our first protocol is statistically secure (i.e. involves a negligible error) in a completely asynchronous setting and improves the communication complexity of the previous best AMPC protocol in the same setting by a factor of Θ(n). Our second protocol is perfectly secure (i.e. error free) in a hybrid setting, where one round of communication is assumed to be synchronous, and improves the communication complexity of the previous best AMPC protocol in the hybrid setting by a factor of Θ(n 2).
Like other efficient MPC protocols, we employ Beaver’s circuit randomization approach (Crypto ’91) and prepare shared random multiplication triples. However, in contrast to previous protocols where triples are prepared by first generating two random shared values which are then multiplied distributively, in our approach each party prepares its own multiplication triples. Given enough such shared triples (potentially partially known to the adversary), we develop a method to extract shared triples unknown to the adversary, avoiding communication-intensive multiplication protocols. This leads to a framework of independent interest.
Full version of the paper available as Cryptology ePrint Archive, Report 2012/517.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
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
Abraham, A., Dolev, D., Halpern, J.: An almost-surely terminating polynomial protocol for asynchronous Byzantine agreement with optimal resilience. In: PODC, pp. 405–414 (2008)
Beaver, D.: Efficient multiparty protocols using circuit randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992)
Beerliová-Trubíniová, 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)
Beerliová-Trubíniová, Z., Hirt, M.: Simple and efficient perfectly-secure asynchronous MPC. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 376–392. Springer, Heidelberg (2007)
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., Canetti, R., Goldreich, O.: Asynchronous secure computation. In: STOC, pp. 52–61 (1993)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: STOC, pp. 1–10 (1988)
Ben-Or, M., Kelmer, B., Rabin, T.: Asynchronous secure computations with optimal resilience. In: PODC, pp. 183–192 (1994)
Ben-Sasson, E., Fehr, S., Ostrovsky, R.: Near-linear unconditionally-secure multiparty computation with a dishonest minority. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 663–680. Springer, Heidelberg (2012)
Bracha, G.: An asynchronous [(n-1)/3]-resilient consensus protocol. In: PODC, pp. 154–162 (1984)
Canetti, R.: Studies in secure multiparty computation and applications. PhD thesis, Weizmann Institute, Israel (1995)
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols. In: STOC, pp. 11–19. ACM (1988)
Damgård, I., Ishai, Y., Krøigaard, M.: Perfectly secure multiparty computation and the computational overhead of cryptography. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 445–465. Springer, Heidelberg (2010)
Damgård, I.B., Nielsen, J.B.: Scalable and unconditionally secure multiparty computation. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 572–590. Springer, Heidelberg (2007)
Dani, V., King, V., Movahedi, M., Saia, J.: Brief announcement: Breaking the \(\mathcal{O}(nm)\) bit barrier, secure multiparty computation with a static adversary. In: PODC, pp. 227–228 (2012)
Franklin, M.K., Yung, M.: Communication complexity of secure computation (extended abstract). In: STOC, pp. 699–710 (1992)
Hirt, M., Maurer, U.M., Przydatek, B.: Efficient secure multi-party computation. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 143–161. Springer, Heidelberg (2000)
MacWilliams, F.J., Sloane, N.J.A.: The theory of error correcting codes. North-Holland Publishing Company (1978)
Patra, A., Choudhury, A., Rangan, C.P.: Communication efficient perfectly secure VSS and MPC in asynchronous networks with optimal resilience. In: Bernstein, D.J., Lange, T. (eds.) AFRICACRYPT 2010. LNCS, vol. 6055, pp. 184–202. Springer, Heidelberg (2010); full version available as Cryptology ePrint Archive, Report 2010/007
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In: STOC, pp. 73–85 (1989)
Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Choudhury, A., Hirt, M., Patra, A. (2013). Asynchronous Multiparty Computation with Linear Communication Complexity. In: Afek, Y. (eds) Distributed Computing. DISC 2013. Lecture Notes in Computer Science, vol 8205. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41527-2_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-41527-2_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41526-5
Online ISBN: 978-3-642-41527-2
eBook Packages: Computer ScienceComputer Science (R0)