A unified framework for concurrent security: universal composability from stand-alone non-malleability

ABSTRACT

We present a unified framework for obtaining Universally Composable (UC) protocols by relying on stand-alone secure non-malleable commitments. Essentially all results on concurrent secure computation--both in relaxed models (e.g., quasi-polynomial time simulation), or with trusted set-up assumptions (e.g., the CRS model, the imperfect CRS model, or the timing model)--are obtained as special cases of our framework. This not only leads to conceptually simpler solutions, but also to improved set-up assumptions, round-complexity, and computational assumptions.

Additionally, this framework allows us to consider new relaxed models of security: we show that UC security where the adversary is a uniform PPT but the simulator is allowed to be a non-uniform PPT (i.e., essentially, traditional UC security, but with a non-uniform reduction) is possible without any trusted set-up. This gives the first results on concurrent secure computation without set-up, which can be used for securely computing "computationally-sensitive" functionalities (e.g., data-base queries, "proof of work"-protocols, or playing bridge on the Internet).

REFERENCES

• 1: B. Barak (Machtey Award Co-winner), How to Go Beyond the Black-Box Simulation Barrier, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.106, October 14-17, 2001
• 2: Boaz Barak , Oded Goldreich, Universal Arguments and their Applications, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.194, May 21-24, 2002
• 3: Boaz Barak , Manoj Prabhakaran , Amit Sahai, Concurrent Non-Malleable Zero Knowledge, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.345-354, October 21-24, 2006 [doi>10.1109/FOCS.2006.21]
• 4: Boaz Barak , Amit Sahai, How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.542-552, October 23-25, 2005 [doi>10.1109/SFCS.2005.43]
• 5: B. Barak and R. Pass. On the Possibility of One-Message Weak Zero-Knowledge. In TCC 2004, pages 121--132.
• 6: Boaz Barak , Ran Canetti , Jesper Buus Nielsen , Rafael Pass, Universally Composable Protocols with Relaxed Set-Up Assumptions, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.186-195, October 17-19, 2004 [doi>10.1109/FOCS.2004.71]
• 7: Donald Beaver, Foundations of Secure Interactive Computing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.377-391, August 11-15, 1991
• 8: R. Canetti. Security and Composition of Multiparty Cryptographic Protocols. Jour. of Cryptology, 13(1):143--202, 2000.
• 9: R. Canetti. Obtaining Universally Composable Security: Towards the Bare Bones of Trust. In Asiacrypt, pages 88--112, 2007.
• 10: 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
• 11: 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
• 12: R. Canetti, E. Kushilevitz and Y. Lindell. On the Limitations of Universally Composable Two-Party Computation Without Set-Up Assumptions. In Eurocrypt2003, Springer LNCS 2656, pages 68--86, 2003.
• 13: R. Canetti, Y. Dodis, R. Pass, S. Walfish. Universally Composable Security with Global Setup. In 4th TCC, 2007
• 14: 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]
• 15: Ran Canetti , Rafael Pass , Abhi Shelat, Cryptography from Sunspots: How to Use an Imperfect Reference String, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.249-259, October 21-23, 2007 [doi>10.1109/FOCS.2007.22]
• 16: Yevgeniy Dodis , Silvio Micali, Parallel Reducibility for Information-Theoretically Secure Computation, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.74-92, August 20-24, 2000
• 17: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 18: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 19: 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]
• 20: A. Feige and A. Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Crypto86, Springer LNCS 263, pages 181--187, 1987.
• 21: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 22: O. Goldreich and A. Kahan. How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. Jour. of Cryptology, Vol. 9, No. 2, pages 167--189, 1996.
• 23: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 24: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 25: Shafi Goldwasser , Leonid A. Levin, Fair Computation of General Functions in Presence of Immoral Majority, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.77-93, August 11-15, 1990
• 26: S. Goldwasser, S. Micali. Probabilistic Encryption. JCSS 28(2), pages 270--299, 1984.
• 27: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 28: J. Groth and R. Ostrovsky. Cryptography in the Multi-string Model. In CRYPTO 2007, pages 323--341, 2007.
• 29: Jonathan Katz, Universally Composable Multi-party Computation Using Tamper-Proof Hardware, Proceedings of the 26th annual international conference on Advances in Cryptology, p.115-128, May 20-24, 2007, Barcelona, Spain [doi>10.1007/978-3-540-72540-4_7]
• 30: J. Katz, R. Ostrovsky and A. Smith. Round Efficiency of Multi-Party Computation with a Dishonest Majority, In EuroCrypt2003. Springer LNCS 2656 pages 578--595, 2003.
• 31: Yael Tauman Kalai , Yehuda Lindell , Manoj Prabhakaran, Concurrent general composition of secure protocols in the timing model, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060687]
• 32: H. Lin, R. Pass, and M. Venkitasubramaniam. Concurrent Non-Malleable Commitments from One-way Functions. In TCC 2008, pages 571--588, 2008.
• 33: Huijia Lin , Rafael Pass, Non-malleability amplification, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536442]
• 34: 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]
• 35: 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
• 36: Silvio Micali, Computationally Sound Proofs, SIAM Journal on Computing, v.30 n.4, p.1253-1298, 2000 [doi>10.1137/S0097539795284959]
• 37: Silvio Micali , Rafael Pass, Local zero knowledge, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132561]
• 38: Silvio Micali , Rafael Pass , Alon Rosen, Input-Indistinguishable Computation, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.367-378, October 21-24, 2006 [doi>10.1109/FOCS.2006.43]
• 39: Silvio Micali , Phillip Rogaway, Secure Computation (Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.392-404, August 11-15, 1991
• 40: R. Ostrovksy, G. Persiano, I. Visconti. Concurrent Non-Malleable Witness Indistinguishability and its applications. http://eccc.hpi-web.de/eccc-reports/2006/TR06-095/ .
• 41: R. Pass. Simulation in Quasi-Polynomial Time and Its Application to Protocol Composition. In EuroCrypt2003, Springer LNCS 2656, pages 160--176, 2003.
• 42: Rafael Pass, Bounded-concurrent secure multi-party computation with a dishonest majority, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007393]
• 43: 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
• 44: Rafael Pass , Alon Rosen, Concurrent Non-Malleable Commitments, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.563-572, October 23-25, 2005 [doi>10.1109/SFCS.2005.27]
• 45: Manoj Prabhakaran , Amit Sahai, New notions of security: achieving universal composability without trusted setup, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007394]
• 46: 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
• 47: Manoj Prabhakaran , Amit Sahai, New notions of security: achieving universal composability without trusted setup, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007394]
• 48: 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
• 49: L. Trevisan , S. Vadhan, Extracting randomness from samplable distributions, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.32, November 12-14, 2000
• 50: Andrew Chi-Chih Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science, p.162-167, October 27-29, 1986 [doi>10.1109/SFCS.1986.25]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

General Terms:
Theory

Keywords:
non-malleability, secure multi-party computation, universal composability