Bounded-concurrent secure two-party computation without setup assumptions

ABSTRACT

In this paper we study the feasibility of obtaining protocols for general two-party computation that remain secure under concurrent composition. (A general protocol can be used for obtaining secure computation of any functionality.) We consider a scenario where no trusted setup is assumed (and so, for example, there is no common reference string available to the parties); we call this the "plain model". We present both negative and positive results for this model. Specifically, we show that a general two-party protocol that remains secure for m concurrent executions and can be proven via black-box simulation, must have more than m rounds of communication. An important corollary of this result is that there do not exist protocols for black-box secure general two-party computation for the case of unbounded concurrency (where any polynomial number of concurrent executions may be run). On the positive side, we show that under general cryptographic assumptions, there exist secure protocols for general two-party computation in the model of bounded concurrent composition (in this model the number of concurrent executions is fixed and the protocol design may depend on this number). Our protocol has O(m) rounds of communication, where m is the bound on the number of concurrent executions, and uses both black-box and non black-box techniques. We note that this protocol constitutes the first feasibility result for general two-party computation without setup assumptions for any model of concurrency.

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: 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
• 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: Ran Canetti , Joe Kilian , Erez Petrank , Alon Rosen, Black-box concurrent zero-knowledge requires \tilde {Ω} (logn) rounds, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.570-579, July 2001, Hersonissos, Greece [doi>10.1145/380752.380852]
• 8: R. Canetti, E. Kushilevitz and Y. Lindell. On the Limitations of Universally Composable Two-Party Computation Without Set-Up Assumptions. In Eurocrypt, 2003.
• 9: 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]
• 10: D. Chaum. Blind Signatures for Untraceable Payments. In CRYPTO'82, pages 199--203, 1982.
• 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: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 13: J. A. Garay , P. MacKenzie, Concurrent oblivious transfer, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.314, November 12-14, 2000
• 14: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 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: 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
• 17: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 18: R. Impagliazzo and M. Luby. One-way Functions are Essential for Complexity Based Cryptography. In 30th FOCS, pages 230--235, 1989.
• 19: 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]
• 20: Joe Kilian , Erez Petrank , Charles Rackoff, Lower Bounds for Zero Knowledge on the Internet, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.484, November 08-11, 1998
• 21: 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
• 22: 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
• 23: R. Richardson and J. Kilian. On the Concurrent Composition of Zero-Knowledge Proofs. In Eurocrypt'99, pages 415--413, 1999.
• 24: 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]
• 25: Alon Rosen, A Note on the Round-Complexity of Concurrent Zero-Knowledge, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.451-468, August 20-24, 2000
• 26: 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:
protocol composition, secure computation