Abstract
Substantial efforts have been spent on characterizing the round complexity of various cryptographic tasks. In this work we study the round complexity of secure multiparty computation in the presence of an active (Byzantine) adversary, assuming the availability of secure point-to-point channels and a broadcast primitive. It was recently shown that in this setting three rounds are sufficient for arbitrary secure computation tasks, with a linear security threshold, and two rounds are sufficient for certain nontrivial tasks. This leaves open the question whether every function can be securely computed in two rounds. We show that the answer to this question is “no”: even some very simple functions do not admit secure 2-round protocols (independently of their communication and time complexity) and thus 3 is the exact round complexity of general secure multiparty computation. Yet, we also present some positive results by identifying a useful class of functions which can be securely computed in two rounds. Our results apply both to the information-theoretic and to the computational notions of security.
Most of this work was done while the author was at AT&T Labs-Research.
Most of this work was done while the author was at IBM T.J. Watson Research Center.
Chapter PDF
Similar content being viewed by others
References
J. Bar-Ilan and D. Beaver. Non-cryptographic fault-tolerant computing in a constant number of rounds. In Proc. 8th ACM PODC, pages 201–209. ACM, 1989.
D. Beaver. Minimal-Latency Secure Function Evaluation. In Eurocrypt’ 00, pages 335–350, 2000. LNCS No. 1807.
D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway. Security with low communication overhead (extended abstract). In Proc. of CRYPTO’ 90.
D. Beaver, S. Micali, and P. Rogaway. The round complexity of secure protocols (extended abstract). In Proc. 22nd STOC, pages 503–513. ACM, 1990.
M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness Theorems for Noncryptographic Fault-Tolerant Distributed Computations. Proc. 20th STOC88, pp. 1–10.
M. Ben-Or and N. Linial. Collective Coin-Flipping. In Randomness and Computation, pages 91–115, 1990.
P. Berman, J. Garay, and K. Perry. Bit Optimal Distributed Consensus. In R. Yaeza-Bates and U. Manber, editors, Computer Science Research, pages 313–322. Plenum Publishing Corporation, 1992.
C. Cachin, J. Camenisch, J. Kilian, and J. Muller. One-round secure computation and secure autonomous mobile agents. In Proceedings of ICALP’00, 2000.
R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143–202, 2000.
D. Chaum, C. Crepeau, and I. Damgard. Multiparty Unconditionally Secure Protocols. In Proc. 20th STOC88, pages 11–19.
R. Cramer and I. Damgøard. Secure distributed linear algebra in a constant number of rounds. In Proc. Crypto 2001.
R. Cramer, I. Damgøard, S. Dziembowski, M. Hirt, and T. Rabin. Efficient multiparty computations with dishonest minority. In Eurocrypt’ 99, pages 311–326, 1999. LNCS No. 1592.
Uri Feige, Joe Kilian, and Moni Naor. A minimal model for secure computation (extended abstract). In Proc. 26th STOC, pages 554–563. ACM, 1994.
P. Feldman and S. Micali. An Optimal Algorithm for Synchronous Byzantine Agreement. SIAM. J. Computing, 26(2):873–933, 1997.
F. Gavril. Manuscript, 1974.
R. Gennaro, S. Halevi, and T. Rabin. Round-optimal zero knowledge with distributed verifiers. http://www.research.ibm.com/security, 2002.
R. Gennaro, Y. Ishai, E. Kushilevitz, and T. Rabin. The Round Complexity of Verifiable Secret Sharing and Secure Multicast. In Proc. 33th STOC. ACM, 2001.
Rosario Gennaro. Achieving Independence Efficiently and Securely. In Proc. 14th ACM PODC, pages 130–136. ACM, 1995.
O. Goldreich. Secure multi-party computation (manuscript). http://www.wisdom.weizmann.ac.il/~oded/pp.html, 1998.
O. Goldreich. Foundation of Cryptography — Fragments of a Book. ECCC 1995. Available online from http://www.eccc.uni-trier.de/eccc/.
O. Goldreich, S. Micali, and A. Wigderson. How to Play Any Mental Game. In Proc. 19th STOC, pages 218–229. ACM, 1987.
Y. Ishai and E. Kushilevitz. Private simultaneous messages protocols with applications. In ISTCS97, pages 174–184, 1997.
Y. Ishai and E. Kushilevitz. Randomizing polynomials: A new representation with applications to round-efficient secure computation. In Proc. 41st FOCS, 2000.
Y. Ishai and E. Kushilevitz. Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials. In Proc. ICALP’ 02.
L. Lamport, R.E. Shostack, and M. Pease. The Byzantine generals problem. ACM Trans. Prog. Lang. and Systems, 4(3):382–401, 1982.
Y. Lindell. Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation. In Crypto’ 01, pages 171–189, 2001. LNCS No. 2139.
N. Lynch. Distributed Algorithms. Morgan Kaufman, 1996.
R. Ostrovsky and M. Yung. How to withstand mobile virus attacks. In Proc. 10th ACM PODC, pages 51–59. ACM, 1991.
M. Pease, R. Shostak, and L. Lamport. Reaching Agreement in the Presence of Faults. Journal of the ACM, 27(2):228–234, 1980.
T. Rabin and M. Ben-Or. Verifiable Secret Sharing and Multiparty Protocols with Honest Majority. In Proc. 21st STOC, pages 73–85. ACM, 1989.
T. Sander, A. Young, and M. Yung. Non-Interactive CryptoComputing For NC1. In Proc. 40th FOCS, pages 554–567. IEEE, 1999.
A. C-C. Yao. How to Generate and Exchange Secrets. In Proc. 27th FOCS, pages 162–167. IEEE, 1986.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T. (2002). On 2-Round Secure Multiparty Computation. In: Yung, M. (eds) Advances in Cryptology — CRYPTO 2002. CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45708-9_12
Download citation
DOI: https://doi.org/10.1007/3-540-45708-9_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44050-5
Online ISBN: 978-3-540-45708-4
eBook Packages: Springer Book Archive