Ran Canetti
Yehuda Lindell
Rafail Ostrovsky
ABSTRACT
We show how to securely realize any multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider a multi-party network with open communication and an adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and make general intractability assumptions.
- D. Beaver Secure Multi-party Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority, Journal of Cryptology, Vol. 4, pp. 75--122, 1991.]]Google Scholar
- D. Beaver, and S. Goldwasser, Multiparty Computation with Faulty Majority, FOCS 89.]]Google Scholar
- M. Ben-Or, S. Goldwasser and A. Wigderson, "Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation", STOC 1998.]] Google ScholarDigital Library
- M. Blum , "Coin flipping by telephone", IEEE Spring COMPCOM, pp. 133--137, Feb. 1982.]]Google Scholar
- M. Blum How to Prove a Theorem So No One Else Can Claim It. Proceedings of the International Congress of (MATH)ematicians, Berkeley, California, USA, 1986, pp. 1444--1451.]]Google Scholar
- M. Blum, P. Feldman and S. Micali, Non-interactive zero-knowledge and its applications. STOC 88.]] Google ScholarDigital Library
- M. Blum, A. De Santis, S. Micali and G. Persiano, Non-Interactive Zero-Knowledge Proofs. SIAM Journal on Computing, vol. 6, December 1991, pp. 1084--1118.]] Google ScholarDigital Library
- G. Brassard, D. Chaum and C. Crépeau, Minimum Disclosure Proofs of Knowledge, JCSS, v. 37, pp 156--189.]] Google ScholarDigital Library
- R. Canetti Security and composition of multi-party cryptographic protocols", Journal of Cryptology, Vol. 13, No. 1, winter 2000.]]Google Scholar
- R. Canetti, "Universally Composable Security: A New paradigm for Cryptographic Protocols", 42nd FOCS, 2001. Full version at http://eprint.iacr.org/2000/067.]]Google Scholar
- R. Canetti, U. Feige, O. Goldreich and M. Naor. Adaptively Secure Multi-Party Computation. STOC 96.]] Google ScholarDigital Library
- R. Canetti and M. Fischlin. Universally Composable Commitments. CRYPTO 01.]] Google ScholarDigital Library
- R. Canetti, Y. Lindell, R. Ostrovsky and A. Sahai. Universally Composable Two-Party and Multiparty Secure Computation. In the ePrint archive: http://eprint.iacr.org.]]Google Scholar
- R. Canetti and T. Rabin. Universal Composition with Joint State. IACR's Eprint archive, http://eprint.iacr.org/2002/.]]Google Scholar
- D. Chaum, C. Crepeau, and I. Damgard, Multiparty Unconditionally Secure Protocols, STOC 88.]] Google ScholarDigital Library
- I. Damgard and J. Nielsen. Improved non-committing encryption schemes based on general complexity assumption. CRYPTO 2000.]] Google ScholarDigital Library
- I. Damgard and J. Nielsen Perfect Hiding or Perfect Binding Universally Composable Commitment Schemes with Constanst Expansion Factor. Manuscrtipt on Damgard homepage, 2001.]]Google Scholar
- Y. Dodis and S. Micali Secure Computation, CRYPTO 2000.]]Google Scholar
- A. DeSantis, G. DiCrescenzo, R. Ostrovsky, G. Persiano, A. Sahai. Robust Non-interactive Zero-Knowledge. CRYPTO 2001.]]Google Scholar
- G. DiCrescenzo, Y. Ishai, and R. Ostrovsky. Non-Interactive and Non-Malleable Commitment. STOC 98.]] Google ScholarDigital Library
- G. DiCrescenzo, J. Katz, R. Ostrovsky and A. Smith Efficient and Non-interactive Non-malleable Commitment, Eurocrypt 2001.]] Google ScholarDigital Library
- A. DeSantis and G. Persiano. Zero-Knowledge Proofs of Knowledge Without Interaction. FOCS 1992.]]Google Scholar
- D. Dolev, C. Dwork and M. Naor, Non-malleable cryptography, SIAM. J. Computing, Vol. 30, No. 2, 2000, pp. 391--437.]] Google ScholarDigital Library
- C. Dwork, M. Naor, and A. Sahai. Concurrent Zero-Knowledge. STOC 1998.]] Google ScholarDigital Library
- S. Even, O. Goldreich and A. Lempel, A randomized protocol for signing contracts, CACM, vol. 28, No. 6, 1985, pp. 637--647.]] Google ScholarDigital Library
- U. Feige and A. Shamir. Zero-Knowledge Proofs of Knowledge in Two Rounds. CRYPTO 1989.]] Google ScholarDigital Library
- U. Feige, D. Lapidot, and A. Shamir, Multiple non-interactive zero knowledge proofs based on a single random string. FOCS 1990.]]Google ScholarDigital Library
- Z. Galil, S, Haber, and M. Yung Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model, Crypto 1987.]] Google ScholarDigital Library
- J. Garay and P. MacKenzie Concurrent Oblivious Transfer, FOCS 2000.]] Google ScholarDigital Library
- O. Goldreich, S. Micali and A. Wigderson, Proofs that Yield Nothing but their Validity or All Languages in NP Have Zero-Knowledge Proof Systems. JACM, Vol. 38, No. 1, pages 691--729, 1991.]] Google ScholarDigital Library
- O. Goldreich. Secure Multi-Party Computation. Manuscript. Preliminary version, 1998. www.wisdom.weizmann.ac.il/~oded/pp.html.]]Google Scholar
- O. Goldreich and L. Levin, A Hard Predicate for All One-way Functions. STOC 1989.]] Google ScholarDigital Library
- O. Goldreich, S. Micali and A. Wigderson. How to Play any Mental Game -- A Completeness Theorem for Protocols with Honest Majority. STOC 1987. For details see {31}.]] Google ScholarDigital Library
- S. Goldwasser, and L. Levin, Fair Computation of General Functions in Presence of Immoral Majority, CRYPTO 1990.]] Google ScholarDigital Library
- S. Goldwasser and S. Micali. Probabilistic Encryption. In JCSS 28(2), pages 270--299, 1984.]]Google ScholarCross Ref
- S. Goldwasser, S. Micali and C. Rackoff, The Knowledge Complexity of Interactive Proof Systems, SIAM Journal on Comput., Vol. 18, No. 1, 1989, pp. 186--208.]] Google ScholarDigital Library
- J. Kilian Uses of Randomness in Algorithms and Protocols, Chapter 3, The ACM Distinghished Dissertation 1989, MIT press.]] Google ScholarDigital Library
- E. Kushilevitz, S. Micali and R. Ostrovsky, Reducibility and Completeness In Multi-Party Private Computations, FOCS 94.]]Google Scholar
- Y. Lindell, A. Lysyanskaya and T. Rabin, On the composition of authenticated Byzantine agreement, STOC 2002.]] Google ScholarDigital Library
- S. Micali and P. Rogaway, Secure Computation, unpublished manuscript, 1992. Preliminary version in CRYPTO '91, LNCS 576, Springer-Verlag, 1991.]]Google Scholar
- M. Naor, Bit Commitment using Pseudorandom Generators. Journal of Cryptology, Vol. 4, pages 151--158, 1991.]]Google Scholar
- B. Pfitzmann and M. Waidner, Composition and integrity preservation of secure reactive systems, 7th ACM Conf. on Computer and Communication Security, 2000, pp. 245--254.]] Google ScholarDigital Library
- M. Rabin, How to exchange secrets by oblivious transfer, Tech. Memo TR-81, Aiken Computation Laboratory, Harvard U., 1981.]]Google Scholar
- T. Rabin and M. Ben-Or Verifiable Secret Sharing and Multi-party Protocols with Honest Majority, STOC 1989.]] Google ScholarDigital Library
- R. Richardson and J. Kilian On the Concurrent Composition of Zero-Knowledge Proofs. Eurocrypt 1999.]]Google Scholar
- A. Sahai Non-Malleable Non-Interactive Zero-Knowledge and Adaptive Chosen-Ciphertext Security. FOCS 1999.]] Google ScholarDigital Library
- A. Yao How to generate and exchange secrets, FOCS 1986.]]Google ScholarDigital Library
Index Terms
- Universally composable two-party and multi-party secure computation
Recommendations
Universally composable quantum multi-party computation
EUROCRYPT'10: Proceedings of the 29th Annual international conference on Theory and Applications of Cryptographic TechniquesThe Universal Composability model (UC) by Canetti (FOCS 2001) allows for secure composition of arbitrary protocols. We present a quantum version of the UC model which enjoys the same compositionality guarantees. We prove that in this model statistically ...
Efficient Fair Secure Two-Party Computation
APSCC '12: Proceedings of the 2012 IEEE Asia-Pacific Services Computing Conference)Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called """"garbled circuit"""". Later, many protocols based on garbled circuit approach have been presented, most ...
On the Limitations of Universally Composable Two-Party Computation Without Set-Up Assumptions
The recently proposed universally composable security framework for analyzing security of cryptographic protocols provides very strong security guarantees. In particular, a protocol proven secure in this framework is guaranteed to maintain its security ...
Comments