Abstract
We revisit the question of secure multiparty computation (MPC) with two rounds of interaction. It was previously shown by Gennaro et al. (Crypto 2002) that 3 or more communication rounds are necessary for general MPC protocols with guaranteed output delivery, assuming that there may be t ≥ 2 corrupted parties. This negative result holds regardless of the total number of parties, even if broadcast is allowed in each round, and even if only fairness is required. We complement this negative result by presenting matching positive results.
Our first main result is that if only one party may be corrupted, then n ≥ 5 parties can securely compute any function of their inputs using only two rounds of interaction over secure point-to-point channels (without broadcast or any additional setup). The protocol makes a black-box use of a pseudorandom generator, or alternatively can offer unconditional security for functionalities in NC1.
We also prove a similar result in a client-server setting, where there are m ≥ 2 clients who hold inputs and should receive outputs, and n additional servers with no inputs and outputs. For this setting, we obtain a general MPC protocol which requires a single message from each client to each server, followed by a single message from each server to each client. The protocol is secure against a single corrupted client and against coalitions of t < n/3 corrupted servers.
The above protocols guarantee output delivery and fairness. Our second main result shows that under a relaxed notion of security, allowing the adversary to selectively decide (after learning its own outputs) which honest parties will receive their (correct) output, there is a general 2-round MPC protocol which tolerates t < n/3 corrupted parties. This protocol relies on the existence of a pseudorandom generator in NC1 (which is implied by standard cryptographic assumptions), or alternatively can offer unconditional security for functionalities in NC1.
Chapter PDF
Similar content being viewed by others
References
Alon, N., Merritt, M., Reingold, O., Taubenfeld, G., Wright, R.N.: Tight bounds for shared memory systems accessed by Byzantine processes. Journal of Distributed Computing 18(2), 99–109 (2005)
Applebaum, B., Ishai, Y., Kushilevitz, E.: Computationally private randomizing polynomials and their applications. Computational Complexity 15(2), 115–162 (2006)
Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. In: Proc. 18th STOC, pp. 150–164 (1986)
Bar-Ilan, J., Beaver, D.: Non-cryptographic fault-tolerant computing in a constant number of rounds. In: Proc. 8th ACM PODC, pp. 201–209 (1989)
Beaver, D.: Minimal-Latency Secure Function Evaluation. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 335–350. Springer, Heidelberg (2000)
Beaver, D., Feigenbaum, J., Kilian, J., Rogaway, P.: Security with low communication overhead (extended abstract). In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 62–76. Springer, Heidelberg (1991)
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: Proc. 22nd STOC, pp. 503–513 (1990)
Beimel, A.: Secure Schemes for Secret Sharing and Key Distribution. Phd. thesis. Dept. of Computer Science (1996)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness Theorems for Noncryptographic Fault-Tolerant Distributed Computations. In: Proc. 20th STOC 1988, pp. 1–10 (1988)
Cachin, C., Camenisch, J., Kilian, J., Muller, J.: One-round secure computation and secure autonomous mobile agents. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, p. 512. Springer, Heidelberg (2000)
Canetti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology 13(1), 143–202 (2000)
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols.cfik03. In: FOCS, pp. 136–145 (2001)
Chaum, D., Crepeau, C., Damgard, I.: Multiparty Unconditionally Secure Protocols. In: Proc. 20th STOC 1988, pp. 11–19 (1988)
Cramer, R., Fehr, S., Ishai, Y., Kushilevitz, E.: Efficient Multi-party Computation over Rings. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 596–613. Springer, Heidelberg (2003)
Choi, S.G., Elbaz, A., Juels, A., Malkin, T., Yung, M.: Two-Party Computing with Encrypted Data. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 298–314. Springer, Heidelberg (2007)
Choi, S.G., Elbaz, A., Malkin, T., Yung, M.: Secure Multi-party Computation Minimizing Online Rounds. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 268–286. Springer, Heidelberg (2009)
Cramer, R., Damgård, I.: Secure distributed linear algebra in a constant number of rounds. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 119. Springer, Heidelberg (2001)
Cramer, R., Damgård, I., Dziembowski, S., Hirt, M., Rabin, T.: Efficient multiparty computations with dishonest minority. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 311–326. Springer, Heidelberg (1999)
Cramer, R., Damgård, I., Ishai, Y.: Share conversion, pseudorandom secret-sharing and applications to secure computation. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 342–362. Springer, Heidelberg (2005)
Cramer, R., Damgård, I., Maurer, U.M.: General Secure Multi-party Computation from any Linear Secret-Sharing Scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 316–334. Springer, Heidelberg (2000)
Damgård, I., Ishai, Y.: Secure multiparty computation using a black-box pseudorandom generator. In: Proc. CRYPTO 2005 (2005)
Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation. In: Proc. 26th STOC, pp. 554–563 (1994)
Fischer, M.J., Lynch, N.A.: A lower bound for the time to assure interactive consistency. Information Processing Letters 14(4), 183–186 (1982)
Fitzi, M., Garay, J.A., Gollakota, S., Rangan, C.P., Srinathan, K.: Round-Optimal and Efficient Verifiable Secret Sharing. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 329–342. Springer, Heidelberg (2006)
Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: The Round Complexity of Verifiable Secret Sharing and Secure Multicast. In: Proc. 33th STOC (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)
Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T.: Protecting Data Privacy in Private Information Retrieval Schemes. In: STOC 1998, pp. 151–160 (1998)
Goldreich, O.: Foundations of Cryptography: Basic Applications. Cambridge University Press, Cambridge (2004)
Goldreich, O., Micali, S., Wigderson, A.: How to Play Any Mental Game. In: Proc. 19th STOC, pp. 218–229 (1987)
Goldwasser, S., Lindell, Y.: Secure Multi-Party Computation without Agreement. J. Cryptology 18(3), 247–287 (2005)
Horvitz, O., Katz, J.: Universally-Composable Two-Party Computation in Two Rounds. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 111–129. Springer, Heidelberg (2007)
Ishai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: ISTCS 1997, pp. 174–184 (1997)
Ishai, Y., Kushilevitz, E.: Randomizing polynomials: A new representation with applications to round-efficient secure computation. In: Proc. 41st FOCS (2000)
Ishai, Y., Kushilevitz, E.: Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, p. 244. Springer, Heidelberg (2002)
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)
Ito, M., Saito, A., Nishizeki, T.: Secret sharing scheme realizing general access structure. Electronics and Communications in Japan, Part III: Fundamental Electronic Science 72(9), 56–64
Jarecki, S., Shmatikov, V.: Efficient Two-Party Secure. Computation on Committed Inputs. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 97–114. Springer, Heidelberg (2007)
Karchmer, M., Wigderson, A.: On Span Programs. In: Proceedings of the 8th Structures in Complexity conference, pp. 102–111 (1993)
Katz, J., Koo, C.-Y.: Round-Efficient Secure Computation in Point-to-Point Networks. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 311–328. Springer, Heidelberg (2007)
Katz, J., Koo, C.-Y., Kumaresan, R.: Improving the Round Complexity of VSS in Point-to-Point Networks. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 499–510. Springer, Heidelberg (2008)
Katz, J., Ostrovsky, R.: Round-Optimal Secure Two-Party Computation. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 335–354. Springer, Heidelberg (2004)
Katz, J., Ostrovsky, R., Smith, A.: Round Efficiency of Multi-party Computation with a Dishonest Majority. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 578–595. Springer, Heidelberg (2003)
Kushilevitz, E., Lindell, Y., Rabin, T.: Information-theoretically secure protocols and security under composition. In: STOC 2006, pp. 109–118 (2006), Full version: Cryptology ePrint Archive, Report 2009/630 (2009)
Lamport, L., Shostack, R.E., Pease, M.: The Byzantine generals problem. ACM Trans. Prog. Lang. and Systems 4(3), 382–401 (1982)
Lindell, Y.: Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 171–189. Springer, Heidelberg (2001)
Lindell, Y., Pinkas, B.: An efficient protocol for secure two-party computation in the presence of malicious adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007)
Lynch, N.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1996)
Pass, R.: Bounded-concurrent secure multi-party computation with a dishonest majority. In: Proc. STOC 2004, pp. 232–241 (2004)
Shamir, A.: How to share a secret. Communications of the ACM 22, 612–613
Patra, A., Choudhary, A., Rabin, T., Rangan, C.P.: The Round Complexity of Verifiable Secret Sharing Revisited. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 487–504. Springer, Heidelberg (2009)
Rabin, T., Ben-Or, M.: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority. In: Proc. 21st STOC, pp. 73–85 (1989)
Sander, T., Young, A., Yung, M.: Non-Interactive CryptoComputing For NC1. In: Proc. 40th FOCS, pp. 554–567. IEEE, Los Alamitos (1999)
Yao, A.C.-C.: How to Generate and Exchange Secrets. In: Proc. 27th FOCS, pp. 162–167. IEEE, Los Alamitos (1986)
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
Ishai, Y., Kushilevitz, E., Paskin, A. (2010). Secure Multiparty Computation with Minimal Interaction. In: Rabin, T. (eds) Advances in Cryptology – CRYPTO 2010. CRYPTO 2010. Lecture Notes in Computer Science, vol 6223. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14623-7_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-14623-7_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14622-0
Online ISBN: 978-3-642-14623-7
eBook Packages: Computer ScienceComputer Science (R0)