Abstract
We consider the central cryptographic task of secure two-party computation: two parties wish to compute some function of their private inputs (each receiving possibly different outputs) where security should hold with respect to arbitrarily-malicious behavior of either of the participants. Despite extensive research in this area, the exact round-complexity of this fundamental problem (i.e., the number of rounds required to compute an arbitrary poly-time functionality) was not previously known.
Here, we establish the exact round complexity of secure two-party computation with respect to black-box proofs of security. We first show a lower bound establishing (unconditionally) that four rounds are not sufficient to securely compute the coin-tossing functionality for any super-logarithmic number of coins; this rules out 4-round protocols for other natural functionalities as well. Next, we construct protocols for securely computing any (randomized) functionality using only five rounds. Our protocols may be based either on certified trapdoor permutations or homomorphic encryption schemes satisfying certain additional properties. The former assumption is implied by, e.g., the RSA assumption for large public exponents, while the latter is implied by, e.g., the DDH assumption. Finally, we show how our protocols may be modified – without increasing their round complexity and without requiring erasures – to tolerate an adaptive malicious adversary.
Chapter PDF
Similar content being viewed by others
Keywords
- Proof System
- Commitment Scheme
- Oblivious Transfer
- Secure Multiparty Computation
- Homomorphic Encryption Scheme
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
Barak, B.: How to Go Beyond the Black-Box Simulation Barrier. In: 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 106–115. IEEE, Los Alamitos (2001)
Barak, B.: Constant-Round Coin-Tossing with a Man-in-the-Middle or Realizing the Shared Random String Model. In: 43rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 345–355. IEEE, Los Alamitos (2002)
Barak, B., Lindell, Y.: Strict Polynomial Time in Simulation and Extraction. In: 34th ACM Symposium on Theory of Computing (STOC), pp. 484–493. ACM, New York (2002)
Bar-Ilan, J., Beaver, D.: Non-Cryptographic Fault-Tolerant Computing in Constant Number of Rounds of Interaction. In: Principles of Distributed Computing, pp. 201–209. ACM, New York (1989)
Beaver, D., Micali, S., Rogaway, P.: The Round Complexity of Secure Protocols. In: 22nd ACM Symposium on Theory of Computing (STOC), pp. 503–513. ACM, New York (1990)
Bellare, M., Micali, S., Ostrovsky, R.: Perfect Zero-Knowledge in Constant Rounds STOC, pp. 482–493 (1990)
Bellare, M., Micali, S., Ostrovsky, R.: The (True) Complexity of Statistical Zero Knowledge STOC, pp. 494–502 (1990)
Blum, M.: Coin Flipping by Phone. In: IEEE COMPCOM, pp. 133–137 (1982)
Canetti, R.: Security and Composition of Multi-Party Cryptographic Protocols. J. Cryptology 13(1), 143–202 (2000)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: STOC 2002, pp. 494–503 (2002)
Canetti, R., Kushilevitz, E., Ostrovsky, R., Rosen, A.: Randomness versus Fault- Tolerance. J. Cryptology 13(1), 107–142 (2000)
Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively-Secure Multiparty Computation. In: 28th ACM Symposium on Theory of Computing (STOC), pp. 639–648. ACM, New York (1996)
Canetti, R., Kilian, J., Petrank, E., Rosen, A.: Concurrent Zero-Knowledge Requires _ Ω (log n) Rounds. In: 33rd ACM Symp. on Theory of Comp (STOC), pp. 570–579. ACM, New York (2001)
Cramer, R., Damgård, I.: Secure Distributed Linear Algebra in a Constant Number of Rounds. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 119–136. Springer, Heidelberg (2001)
Di Crescenzo, G., Ostrovsky, R.: On Concurrent Zero-Knowledge with Preprocessing. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 485–502. Springer, Heidelberg (1999)
Damgård, I., Nielsen, J.B.: Improved Non-Committing Encryption Schemes. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 432–450. Springer, Heidelberg (2000)
De Santis, A., DiCrescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust Noninteractive Zero Knowledge. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 566–598. Springer, Heidelberg (2001)
Feige, U.: Alternative Models for Zero Knowledge Interactive Proofs. PhD thesis, Weizmann Institute of Science (1990)
Feige, U., Shamir, A.: Zero Knowledge Proofs of Knowledge in Two Rounds. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 526–544. Springer, Heidelberg (1990)
Feige, U., Shamir, A.: Witness Indistinguishability and Witness Hiding Protocols. In: 22nd ACM Symposium on Theory of Computing (STOC), pp. 416–426. ACM, New York (1990)
Fitzi, M., Garay, J., Maurer, U., Ostrovsky, R.: Minimal Complete Primitives for Secure Multi-party Computation. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 80–100. Springer, Heidelberg (2001)
Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: The Round Complexity of Verifiable Secret Sharing and Secure Multicast. In: 33rd ACM Symposium on Theory of Computing (STOC), pp. 580–589. ACM, New York (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)
Goldreich, O.: Foundations of Cryptography. Basic Tools, vol. 1. Cambridge University Press, Cambridge (2001)
Goldreich, O.: Draft of a Chapter on Cryptographic Protocols (June 2003), Available at http://www.wisdom.weizmann.ac.il/~oded/foc-vol2.html
Goldreich, O.: Draft of an Appendix Regarding Corrections and Additions (June 2003), Available at http://www.wisdom.weizmann.ac.il/~oded/foc-vol2.html
Goldreich, O., Kahan, A.: How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. J. Cryptology 9(3), 167–190 (1996)
Goldreich, O., Krawczyk, H.: On the Composition of Zero-Knowledge Proof Systems. SIAM J. Computing 25(1), 169–192 (1996)
Goldreich, O., Micali, S., Wigderson, A.: How to Play any Mental Game: a Completeness Theorem for Protocols with Honest Majority. In: 19th ACM Symposium on Theory of Computing (STOC), pp. 218–229. ACM, New York (1987)
Impagliazzo, R., Rudich, S.: Limits on the Provable Consequences of One-Way Permutations. In: 21st ACM Symposium on Theory of Computing (STOC), pp. 44–61. ACM, New York (1989)
Kilian, J., Kushilevitz, E., Micali, S., Ostrovsky, R.: Reducibility and Completeness in Private Computations. SIAM J. Comput. 29(4), 1189–1208 (2000)
Ishai, Y., Kushilevitz, E.: Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation. In: 41st IEEE Symposium on Foundations of Computer Science (FOCS), pp. 294–304. IEEE, Los Alamitos (2000)
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., Ostrovsky, R., Rosén, A.: Amortizing Randomness in Private Multiparty Computations. SIAM J. Discrete Math. 16(4), 533–544 (2003)
Kilian, J., Petrank, E.: Concurrent and Resettable Zero-Knowledge in Polylogarithmic Rounds. In: 31st ACM Symposium on Theory of Computing (STOC), pp. 560–569. ACM, New York (2001)
Lapidot, D., Shamir, A.: Publicly-Verifiable Non-Interactive Zero-Knowledge Proofs. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 353–365. Springer, Heidelberg (1991)
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.: Personal communication (2001)
Micali, S., Rogaway, P.: Secure Computation. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 392–404. Springer, Heidelberg (1992)
Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 196–214. Springer, Heidelberg (1993)
Prabhakaran, M., Rosen, A., Sahai, A.: Concurrent Zero Knowledge with Logarithmic Round-Complexity. In: 43rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 366–375. IEEE, Los Alamitos (2002)
Richardson, R., Kilian, J.: On the Concurrent Composition of Zero-Knowledge Proofs. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 415–431. Springer, Heidelberg (1999)
Yao, A.C.: How to Generate and Exchange Secrets. In: 27th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 162–167. IEEE, Los Alamitos (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Katz, J., Ostrovsky, R. (2004). Round-Optimal Secure Two-Party Computation. In: Franklin, M. (eds) Advances in Cryptology – CRYPTO 2004. CRYPTO 2004. Lecture Notes in Computer Science, vol 3152. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28628-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-28628-8_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22668-0
Online ISBN: 978-3-540-28628-8
eBook Packages: Springer Book Archive