New notions of security: achieving universal composability without trusted setup

ABSTRACT

We propose a modification to the framework of Universally Composable (UC) security [3]. Our new notion involves comparing the real protocol execution with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [3] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework.

REFERENCES

• 1: Boaz Barak, Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.345-355, November 16-19, 2002
• 2: Boaz Barak and Yehuda Lindell. Strict Polynomial-time in Simulation and Extraction. Electronic Colloquium on Computational Complexity (ECCC)(026): (2002)
• 3: R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001
• 4: Ran Canetti , Marc Fischlin, Universally Composable Commitments, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.19-40, August 19-23, 2001
• 5: Ran Canetti , Hugo Krawczyk, Universally Composable Notions of Key Exchange and Secure Channels, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.337-351, May 02, 2002
• 6: R. Canetti, E. Kushilevitz, and Y. Lindell. On the limitations of universally composable two-party computation without set-up assumptions. In EUROCRYPT, pages 68--86, 2003.
• 7: Ran Canetti , Yehuda Lindell , Rafail Ostrovsky , Amit Sahai, Universally composable two-party and multi-party secure computation, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509980]
• 8: Ivan Damgard , Jens Groth, Non-interactive and reusable non-malleable commitment schemes, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780605]
• 9: Giovanni Di Crescenzo , Yuval Ishai , Rafail Ostrovsky, Non-interactive and non-malleable commitment, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.141-150, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276722]
• 10: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 11: Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.409-418, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276853]
• 12: Shafi Goldwasser , Yehuda Lindell, Secure Computation without Agreement, Proceedings of the 16th International Conference on Distributed Computing, p.17-32, October 28-30, 2002
• 13: Secure Multi-Party Computation. Manuscript. Preliminary version, 1998. Available from: http://www. wisdom. weizmann. ac. il/ oded/pp. html.
• 14: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 15: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 16: Joe Kilian , Erez Petrank, Concurrent and resettable zero-knowledge in poly-loalgorithm rounds, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.560-569, July 2001, Hersonissos, Greece [doi>10.1145/380752.380851]
• 17: Yehuda Lindell, Bounded-concurrent secure two-party computation without setup assumptions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780641]
• 18: Yehuda Lindell, General Composition and Universal Composability in Secure Multi-Party Computation, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.394, October 11-14, 2003
• 19: Moni Naor. Bit Commitment using Pseudorandom Generators. Journal of Cryptology, 4(2):151--158, 1991.
• 20: Rafael Pass. Simulation in Quasi-Polynomial Time, and Its Application to Protocol Composition. EUROCRYPT 2003: 160--176.
• 21: Rafael Pass , Alon Rosen, Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.404, October 11-14, 2003
• 22: Birgit Pfitzmann , Michael Waidner, Composition and integrity preservation of secure reactive systems, Proceedings of the 7th ACM conference on Computer and communications security, p.245-254, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352639]
• 23: Birgit Pfitzmann , Michael Waidner, A Model for Asynchronous Reactive Systems and its Application to Secure Message Transmission, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.184, May 14-16, 2001
• 24: Manoj Prabhakaran , Alon Rosen , Amit Sahai, Concurrent Zero Knowledge with Logarithmic Round-Complexity, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.366-375, November 16-19, 2002
• 25: Manoj Prabhakaran and Amit Sahai. New Notions of Security: Achieving Universal Composability without Trusted Setup. At the Cryptology ePrint Archive http://eprint. iacr. org/. 2004.
• 26: Manoj Prabhakaran and Amit Sahai. Revisiting Concurrency: Monitored Functionalities and Client-Server Computation. Manuscript under preparation.
• 27: Amit Sahai, Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.543, October 17-18, 1999
• 28: Ransom Richardson and Joe Kilian. On the Concurrent Composition of Zero-Knowledge Proofs. EUROCRYPT 1999: 415--431
• 29: J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100269]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Security, Theory

Keywords:
environmental security, general composition, generalized environmental security, secure multi-party computation, secure protocols, simulation, universal composability