Paper 2006/455

On Achieving the ''Best of Both Worlds'' in Secure Multiparty Computation

Jonathan Katz


Two settings are typically considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Protocols designed under this assumption provide full security (and, in particular, guarantee output delivery and fairness) when this assumption is correct; however, if half or more of the parties are dishonest then security is completely compromised. On the other hand, protocols tolerating arbitrarily-many faults do not provide fairness or guaranteed output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the ''best of both worlds''; namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Ishai, et al. (Crypto 2006) recently addressed this question, and ruled out constant-round protocols of this type. As our main result, we completely settle the question by ruling out protocols using any (expected) polynomial number of rounds. Given this stark negative result, we 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 holds for logarithmic-round protocols. We also show, for any polynomial $p$, a protocol (whose round complexity depends on $p$) that can be simulated to within closeness $O(1/p)$.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
secure computationfairness
Contact author(s)
jkatz @ cs umd edu
2007-01-08: last of 3 revisions
2006-12-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jonathan Katz},
      title = {On Achieving the ''Best of Both Worlds'' in Secure Multiparty Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2006/455},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.