Concurrent general composition of secure protocols in the timing model

ABSTRACT

In the setting of secure multiparty computation, a set of mutually distrustful parties wish to jointly compute some function of their input (i.e., they wish to securely carry out some distributed task). %The joint computation should be such that even In the stand-alone case, it has been shown that every efficient function can be securely computed. However, in the setting of concurrent composition, broad impossibility results have been proven for the case where there is no honest majority (or trusted setup).In this paper, we investigate the feasibility of obtaining secure multiparty protocols in a network where certain time bounds are assumed. Specifically, the security of our protocols rely on the very reasonable assumption that local clocks do not "drift" too much (i.e., it is assumed that they proceed at approximately the same rate). We show that under this mild timing assumption, it is possible to securely compute any functionality under concurrent general composition (as long as messages from the arbitrary other protocols are delayed for a specified amount of time).

REFERENCES

• 1: Boaz Barak , Yehuda Lindell , Salil Vadhan, Lower Bounds for Non-Black-Box Zero Knowledge, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.384, October 11-14, 2003
• 2: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 3: Coin Flipping by Phone. IEEE Spring COMPCOM, pages 133--137, 1982.
• 4: R. Canetti. Security and Composition of Multiparty Cryptographic Protocols. Journal of Cryptology, 13(1):143--202, 2000.
• 5: 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
• 6: 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
• 7: R. Canetti, E. Kushilevitz and Y. Lindell. On the Limitations of Universal Composable Two-Party Computation Without Set-Up Assumptions. In EUROCRYPT'03, Springer-Verlag (LNCS 2656), pages 68--86, 2003.
• 8: 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]
• 9: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 10: Benny Chor , Michael O. Rabin, Achieving independence in logarithmic number of rounds, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.260-268, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41862]
• 11: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 12: Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Journal of the ACM (JACM), v.51 n.6, p.851-898, November 2004 [doi>10.1145/1039488.1039489]
• 13: C. Dwork , M. Naor, Zaps and their applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.283, November 12-14, 2000
• 14: Cynthia Dwork , Amit Sahai, Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.442-457, August 23-27, 1998
• 15: Uriel Feige , Adi Shamir, Zero Knowledge Proofs of Knowledge in Two Rounds, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.526-544, August 20-24, 1989
• 16: U. Feige , A. Shamir, Witness indistinguishable and witness hiding protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.416-426, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100272]
• 17: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 18: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 19: Oded Goldreich, Concurrent zero-knowledge with timing, revisited, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509959]
• 20: 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]
• 21: Shafi Goldwasser , Yehuda Lindell, Secure Computation without Agreement, Proceedings of the 16th International Conference on Distributed Computing, p.17-32, October 28-30, 2002
• 22: 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]
• 23: Y. Kalai, Y. Lindell and M. Prabhakharan. Concurrent General Composition of Secure Protocols in the Timing Model (full version). Cryptology ePrint Archive, report 2005/036.
• 24: J. Katz. Efficient and Non-malleable Proofs of Plaintext Knowledge and Applications. In EUROCRYPT 2003, Springer-Verlag (LNCS 2656), pages 211--228, 2003.
• 25: Y. Lindell. Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation. Journal of Cryptology, 16(3):143--184, 2003.
• 26: 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]
• 27: 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
• 28: Y. Lindell. Lower Bounds for Concurrent Self Composition. In the 1st Theory of Cryptography Conference (TCC), Springer-Verlag (LNCS 2951), pages 203--222, 2004.
• 29: M. Naor. Bit Commitment using Pseudorandom Generators. Journal of Cryptology, 4(2):151--158, 1991.
• 30: R. Pass. Simulation in Quasi-Polynomial Time, and Its Application to Protocol Composition. In Eurocrypt 2003, Springer-Verlag (LNCS 2656), pages 160--176, 2003.
• 31: 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]
• 32: 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
• 33: 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]
• 34: 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]
• 35: R. Richardson and J. Kilian. On the Concurrent Composition of Zero-Knowledge Proofs. In EUROCRYPT'99, Springer-Verlag (LNCS 1592), pages 415--431, 1999.
• 36: A. Yao. How to Generate and Exchange Secrets. In 27th FOCS, pages 162--167, 1986.

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:
cryptography, protocol composition, secure multiparty computation