Paper 2020/1170

On the Power of an Honest Majority in Three-Party Computation Without Broadcast

Bar Alon, Ran Cohen, Eran Omri, and Tom Suad

Abstract

Fully secure multiparty computation (MPC) allows a set of parties to compute some function of their inputs, while guaranteeing correctness, privacy, fairness, and output delivery. Understanding the necessary and sufficient assumptions that allow for fully secure MPC is an important goal. Cleve (STOC'86) showed that full security cannot be obtained in general without an honest majority. Conversely, by Rabin and Ben-Or (STOC'89), assuming a broadcast channel and an honest majority enables a fully secure computation of any function. Our goal is to characterize the set of functionalities that can be computed with full security, assuming an honest majority, but no broadcast. This question was fully answered by Cohen et al. (TCC'16) -- for the restricted class of symmetric functionalities (where all parties receive the same output). Instructively, their results crucially rely on agreement and do not carry over to general asymmetric functionalities. In this work, we focus on the case of three-party asymmetric functionalities, providing a variety of necessary and sufficient conditions to enable fully secure computation. An interesting use-case of our results is server-aided computation, where an untrusted server helps two parties to carry out their computation. We show that without a broadcast assumption, the resource of an external non-colluding server provides no additional power. Namely, a functionality can be computed with the help of the server if and only if it can be computed without it. For fair coin tossing, we further show that the optimal bias for three-party (server-aided) $r$-round protocol remains $\Theta(1/r)$ (as in the two-party setting).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2020
Keywords
broadcastpoint-to-point communicationmultiparty computationcoin flippingimpossibility resulthonest majority
Contact author(s)
alonbar08 @ gmail com
rancohen @ ccs neu edu
omrier @ ariel ac il
tomsuad7 @ gmail com
History
2021-06-13: last of 3 revisions
2020-09-25: received
See all versions
Short URL
https://ia.cr/2020/1170
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1170,
      author = {Bar Alon and Ran Cohen and Eran Omri and Tom Suad},
      title = {On the Power of an Honest Majority in Three-Party Computation Without Broadcast},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1170},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1170}},
      url = {https://eprint.iacr.org/2020/1170}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.