Abstract
A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally Composable (UC) security provides this guarantee in a strong sense: A UC-secure protocol maintains its security properties even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, many interesting cryptographic tasks are provably impossible to realize with UC security, unless some trusted set-up is assumed. Impossibility holds even if ideally authenticated communication channels are provided.
This survey examines and compares a number of set-up assumptions (models) that were recently demonstrated to suffice for constructing UC-secure protocols that realize practically any cryptographic task. We start with the common reference string (CRS) and key registration (KR) models. We then proceed to the “sunspot” models, which allow for some adversarial control over the set-up, a number of models which better captures set-up that is globally available in the system, and a timing assumption. Finally, we briefly touch upon set-up models for obtaining authenticated communication.
This survey complements a talk given by the author at this conference. Work supported by NSF grants CT-0430450 and CFF-0635297, and US-Israel Binational Science Foundation Grant 2006317.
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
Ateniese, G., de Medeiros, B.: Identity-based Chameleon Hash and Applications. In: Proc. of Financial Cryptography (2004), available at http://eprint.iacr.org/2003/167/
Barak, B.: How to go Beyond the Black-Box Simulation Barrier. In: 42nd FOCS, pp. 106–115 (2001)
Barak, B., Canetti, R., Nielsen, J.B., Pass, R.: Universally Composable Protocols with Relaxed Set-Up Assumptions. In: 45th FOCS, pp. 186–195 (2004)
Barak, B., Lindell, Y.: Strict polynomial-time in simulation and extraction. SIAM J. Comput 33(4), 738–818 (2004)
Barak, B., Sahai, A.: How To Play Almost Any Mental Game Over the Net - Concurrent Composition via Super-Polynomial Simulation. In: 46th FOCS (2005)
Beaver, D.: Secure Multi-party Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority. J. Cryptology 4, 75–122 (1991)
Ben-Or, M., Canetti, R., Goldreich, O.: Asynchronous Secure Computation. In: 25th Symposium on Theory of Computing (STOC), 1993, pp. 52–61. Longer version appears in TR #755, CS dept., Technion (1992)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation. In: STOC. 20th Symposium on Theory of Computing, pp. 1–10. ACM, New York (1988)
Ben-Or, M., Kelmer, B., Rabin, T.: Asynchronous Secure Computations with Optimal Resilience. In: 13th PODC, pp. 183–192 (1994)
Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: STOC 1988, pp. 103–112 (1988)
Canetti, R.: Security and composition of multi-party cryptographic protocols. J. Cryptology 13(1) (2000)
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. Extended abstract in 42nd FOCS, 2001. A revised version is available at IACR Eprint Archive, eprint.iacr.org/2000/067/ and at the ECCC archive (2005), http://eccc.uni-trier.de/eccc-reports/2001/TR01-016/
Canetti, R.: Universally Composable Signature, Certification, and Authentication. In: 17th Computer Security Foundations Workshop (CSFW), Long version at eprint.iacr.org/2003/239 (2004)
Canetti, R.: Security and composition of cryptographic protocols: A tutorial. SIGACT News, vol. 37(3 & 4), Available also at the Cryptology ePrint Archive, Report 2006/465 (2006)
Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally Composable Security with Pre-Existing Setup. In: 4th theory of Cryptology Conference (TCC) (2007)
Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively Secure Computation. In: STOC. 28th Symposium on Theory of Computing, ACM, New York (1996) (Fuller version in MIT-LCS-TR 682, 1996)
Canetti, R., Fischlin, M.: Universally Composable Commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, Springer, Heidelberg (2001)
Canetti, R., Kushilevitz, E., Lindell, Y.: On the Limitations of Universally Composable Two-Party Computation without Set-up Assumptions. In: Biham, E. (ed.) Advances in Cryptology – EUROCRPYT 2003. LNCS, vol. 2656, pp. 68–86. Springer, Heidelberg (2003)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: 34th STOC, pp. 494–503 (2002)
Canetti, R., Pass, R., shelat, A.: Cryptography from sunspots: How to use an imperfect reference string. In: STOC. 39th Symposium on Theory of Computing, ACM, New York (2007)
Canetti, R., Rabin, T.: Universal Composition with Joint State. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, Springer, Heidelberg (2003)
Datta, A., Derek, A., Mitchell, J.C., Ramanathan, A., Scedrov, A.: Games and the Impossibility of Realizable Ideal Functionality. In: 3rd theory of Cryptology Conference (TCC) (2006)
Dodis, Y., Ong, S., Prabhakaran, M., Sahai, A.: On the (im)possibility of cryptography with imperfect randomness. In: FOCS 2004, pp. 196–205 (2004)
Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. SIAM. J. Computing. vol. 30(2), pp. 391-437 (2000). Preliminary version in 23rd Symposium on Theory of Computing (STOC) (1991)
Dwork, C., Naor, M., Sahai, A.: Concurrent Zero-Knowledge. In: 30th STOC, pp. 409–418 (1998)
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)
Forges, F.: Can sunspots replace a mediator? J. of Math. Ec. 17(4), 347–368 (1988)
Gennaro, R., Rabin, M., Rabin, T.: Simplified VSS and Fast-track Multiparty Computations with Applications to Threshold Cryptography. In: 17th PODC, pp. 101–112 (1998)
Goldreich, O., Krawczyk, H.: On the Composition of Zero-Knowledge Proof Systems. SIAM. J. Computing 25(1) (1996)
Goldreich, O., Micali, S., Wigderson, A.: How to Play any Mental Game. In: 19th Symposium on Theory of Computing (STOC), pp. 218–229 (1987)
Goldwasser, S., Levin, L.: Fair Computation of General Functions in Presence of Immoral Majority. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, Springer, Heidelberg (1991)
Hofheinz, D., Muller-Quade, J., Unruh, D.: Universally Composable Zero-Knowledge Arguments and Commitments from Signature Cards. Tatra Mountains Mathematical Publications (2005)
Kelsey, J., Schneier, B., Wagner, D.: Protocol Interactions and the Chosen Protocol Attack. In: Security Protocols Workshop, pp. 91–104 (1997)
Kushilevitz, E., Lindell, Y., Rabin, T.: Information-Theoretically Secure Protocols and Security Under Composition. In: 38th STOC, pp. 109–118 (2006)
Lindell, Y.: General Composition and Universal Composability in Secure Multi-Party Computation. In: 43rd FOCS, pp. 394–403 (2003)
Lindell, Y.: Lower Bounds for Concurrent Self Composition. In: 1st Theory of Cryptology Conference (TCC), pp. 203–222 (2004)
Lindell, Y., Prabhakaran, M., Tauman, Y.: Concurrent General Composition of Secure Protocols in the Timing Model. Manuscript (2004)
Malkin, T., Moriarty, R., Yakovenko, N.: Generalized Environmental Security from Number Theoretic Assumptions. In: 3rd Theory of Cryptology Conference (TCC), pp. 343–359 (2006)
Micali, S., Rogaway, P.: Secure Computation. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, Springer, Heidelberg (1992)
Pass, R.: On Deniabililty in the Common Reference String and Random Oracle Model. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 216–337. Springer, Heidelberg (2003)
Pfitzmann, B., Waidner, M.: Composition and integrity preservation of secure reactive systems. In: 7th ACM Conf. on Computer and Communication Security (CCS), pp. 245–254 (2000)
Pfitzmann, B., Waidner, M.: A model for asynchronous reactive systems and its application to secure message transmission. IEEE Symposium on Security and Privacy, May 2001, IBM Research, Zurich (December 2000), Preliminary version in and IBM Research Report RZ 3304 (#93350) http://eprint.iacr.org/2000/066
Prabhakaran, M., Sahai, A.: New notions of security: achieving universal composability without trusted setup. In: 36th STOC, pp. 242–251 (2004)
Rabin, T., Ben-Or, M.: Verifiable Secret Sharing and Multi-party Protocols with Honest Majority. In: 21st Symposium on Theory of Computing (STOC), pp. 73–85 (1989)
Trevisan, L., Vadhan, S.: Extracting randomness from samplable distributions. In: FOCS 2000, pp. 32–42 (2000)
Yao, A., Yao, F.F., Zhao, Y.: A Note on Universal Composable Zero Knowledge in Common Reference String Model. In: TAMC 2007, pp. 462–473 (2007)
Yao, A., Yao, F.F., Zhao, Y.: A Note on the Feasibility of Generalized Universal Composability. In: TAMC 2007, pp. 474–485 (2007)
Zhang, F., Safavi-Naini, R., Susilo, W.: ID-Based Chameleon Hashes from Bilinear Pairings. available at http://eprint.iacr.org/2003/208/
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Canetti, R. (2007). Obtaining Universally Compoable Security: Towards the Bare Bones of Trust. In: Kurosawa, K. (eds) Advances in Cryptology – ASIACRYPT 2007. ASIACRYPT 2007. Lecture Notes in Computer Science, vol 4833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-76900-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-76900-2_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-76899-9
Online ISBN: 978-3-540-76900-2
eBook Packages: Computer ScienceComputer Science (R0)