Abstract
Cryptographic systems often involve running multiple concurrent instances of some protocol, where the instances have some amount of joint state and randomness. (Examples include systems where multiple protocol instances use the same public-key infrastructure, or the same common reference string.) Rather than attempting to analyze the entire system as a single unit, we would like to be able to analyze each such protocol instance as stand-alone, and then use a general composition theorem to deduce the security of the entire system. However, no known composition theorem applies in this setting, since they all assume that the composed protocol instances have disjoint internal states, and that the internal random choices in the various executions are independent. We propose a new composition operation that can handle the case where different components have some amount of joint state and randomness, and demonstrate sufficient conditions for when the new operation preserves security. The new operation, which is called universal composition with joint state (and is based on the recently proposed universal composition operation), turns out to be very useful in a number of quite different scenarios such as those mentioned above.
Chapter PDF
Similar content being viewed by others
References
Beaver, D.: Secure Multiparty Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority. Journal of Cryptology 4, 75–122 (1991)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness Theorems for Noncryptographic Fault-Tolerant Distributed Computations. In: Proc. 20th STOC, pp. 1–10. ACM, New York (1988)
Blum, M.: Coin Flipping by Telephone. In: IEEE Spring COMPCOM, pp. 133–137 (1982)
Bellare, M., Rogaway, P.: Entity Authentication and Key Distribution. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 232–249. Springer, Heidelberg (1994)
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. In: Proc. 42st FOCS, pp. 136–145. IEEE, Los Alamitos (2001), http://eprint.iacr.org/2000/067
Canetti, R., Fischlin, M.: Universally Composable Commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001)
Canetti, R., Krawczyk, H.: Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 453–474. Springer, Heidelberg (2001)
Canetti, R., Krawczyk, H.: Universally Composable Key Exchange and Secure Channels. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 337–351. Springer, Heidelberg (2002)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally Composable Two-Party and Multi-Party Secure Computation. In: Proc. 34th STOC, pp. 494–503.
Canetti, R., Rabin, T.: Universal Composition with Joint State. Available online, http://eprint.iacr.org
De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust non-interactive zero knowledge. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 566. Springer, Heidelberg (2001)
Dolev, D., Dwork, C., Naor, M.: Non-malleable Cryptography. SIAM J. Comput. 30(2), 391–437 (2000)
Dodis, Y., Micali, S.: Parallel Reducibility for Information-Theoretically Secure Computation. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 74–92. Springer, Heidelberg (2000)
Damgard, I., Nielsen, J.: Universally Composable Commitment Schemes with Constant Expansion Factor. In: CRYPTO 2002. LNCS, vol. 2442 (2002)
Dwork, C., Naor, M., Sahai, A.: Concurrent zero-knowledge. In: Proc. 30th STOC, pp. 409–418
Goldreich, O., Krawczyk, H.: On the composition of zero-knowledge proof systems. SIAM. J. Computing 25(1), 169–192 (1996)
Goldwasser, S., Levin, L.: Fair computation of general functions in presence of immoral majority. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 77–93. Springer, Heidelberg (1991)
Goldreich, O., Micali, S., Wigderson, A.: How to Play Any Mental Game. In: Proc. 19th STOC, pp. 218–229. ACM, New York (1987)
Goldreich, O., Oren, Y.: Definitions and Properties of Zero-Knowledge Proof Systems. Journal of Cryptology 7(1), 1–32 (1994); Preliminary version by Y. Oren in FOCS87
Goldreich, O.: Concurrent Zero-Knowledge With Timing Revisited. In: Proc. 34th STOC
Lindell, Y., Lysyanskya, A., Rabin, T.: On the Composition of Authenticated Byzantine Agreement. In: Proc. 34th STOC, pp. 514–523.
Micali, S., Rogaway, P.: Secure Computation. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 392–404. Springer, Heidelberg (1992) (Manuscript available)
Pfitzmann, B., Schunter, M., Waidner, M.: Secure Reactive Systems. IBM Research Report RZ 3206 (#93252), IBM Research, Zurich (May 2000)
Shoup, V.: On Formal Models for Secure Key Exchange(1999), Available at, http://www.shoup.org
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Canetti, R., Rabin, T. (2003). Universal Composition with Joint State. In: Boneh, D. (eds) Advances in Cryptology - CRYPTO 2003. CRYPTO 2003. Lecture Notes in Computer Science, vol 2729. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45146-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-45146-4_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40674-7
Online ISBN: 978-3-540-45146-4
eBook Packages: Springer Book Archive