On achieving the "best of both worlds" in secure multiparty computation

ABSTRACT

Two settings are typically considered for secure multipartycomputation, depending on whether or not a majority of the partiesare assumed to be honest. Protocols designed under this assumptionprovide "full security" (and, in particular, guarantee outputdelivery and fairness) when this assumption is correct; however, if half or more of the parties are dishonest then security iscompletely compromised. On the other hand, protocols toleratingarbitrarily-many faults do not provide fairness or guaranteed output delivery even if only a single party is dishonest. It isnatural to wonder whether it is possible to achieve the "best ofboth worlds" : namely, a single protocol that simultaneouslyachieves the best possible security in both the above settings. Ishai, et al. (Crypto 2006) recently addressed this question, andruled out constant-round protocols of this type.

As our main result, we completely settle the question by ruling outprotocols using any (expected) polynomial number of rounds. Given this stark negative result, we then ask what can be achieved if we are willing to assume simultaneous message transmission (or, equivalently, a non-rushing adversary). In this setting, we show that impossibility still holdsfor logarithmic-round protocols. We also show, for any polynomialp, a protocol (whose round complexity depends on p) that can be simulated to within closeness O(1/p).

REFERENCES

• 1: Donald Beaver, Multiparty Protocols Tolerating Half Faulty Processors, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.560-572, August 20-24, 1989
• 2: D. Beaver and S. Goldwasser. Multiparty Computation with Faulty Majority. FOCS '89.
• 3: D. Beaver , S. Micali , P. Rogaway, The round complexity of secure protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.503-513, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100287]
• 4: 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]
• 5: Dan Boneh , Moni Naor, Timed Commitments, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.236-254, August 20-24, 2000
• 6: R. Canetti. Security and Composition of Multiparty Cryptographic Protocols. J. Cryptology 13(1): 143--202, 2000.
• 7: 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]
• 8: R Cleve, Limits on the security of coin flips when half the processors are faulty, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.364-369, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12168]
• 9: Richard Cleve, Controlled Gradual Disclosure Schemes for Random Bits and Their Applications, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.573-588, August 20-24, 1989
• 10: 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]
• 11: Matthias Fitzi , Martin Hirt , Ueli M. Maurer, Trading Correctness for Privacy in Unconditional Multi-Party Computation (Extended Abstract), Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.121-136, August 23-27, 1998
• 12: M. Fitzi, M. Hirt, T. Holenstein, and J. Wullschleger. Two-Threshold Broadcast and Detectable Multiparty Computation. Eurocrypt 2003.
• 13: M. Fitzi, M. Hirt, and J. Wullschleger. Multiparty Computation with Hybrid Security. Eurocrypt 2004.
• 14: J. Garay, P. MacKenzie, M. Prabhakaran, and K. Yang. Resource Fairness and Composability of Cryptographic Protocols. TCC 2006.
• 15: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 16: 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]
• 17: 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
• 18: S. Goldwasser and Y. Lindell. Secure Multiparty Computation without Agreement. J. Cryptology 18(3): 247--287, 2005.
• 19: Y. Ishai, E. Kushilevitz, Y. Lindell, and E. Petrank. On Combining Privacy with Guaranteed Output Delivery in Secure Multiparty Computation. Crypto 2006.
• 20: J. Katz. On Achieving the "Best of Both Worlds" in Secure Multiparty Computation. Available at http://eprint.iacr.org/2006/455.
• 21: J. Katz, R. Ostrovsky, and A. Smith. Round Efficiency of Multi-Party Computation with a Dishonest Majority. Eurocrypt 2003.
• 22: M. Luby, S. Micali, and C. Rackoff. How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin. FOCS '83.
• 23: 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]
• 24: B. Pinkas. Fair Secure Two-Party Computation. Eurocrypt 2003.
• 25: T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
• 26: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 27: A. Yao. How to Generate and Exchange Secrets. FOCS '86.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Security, Theory

Keywords:
secure computation