You are looking at a specific version 20160706:131853 of this paper. See the latest version.

Paper 2015/846

Characterization of Secure Multiparty Computation Without Broadcast

Ran Cohen and Iftach Haitner and Eran Omri and Lior Rotem

Abstract

A major challenge in the study of cryptography is characterizing the necessary and sufficient assumptions required to carry out a given cryptographic task. The focus of this work is the necessity of a broadcast channel for securely computing symmetric functionalities (where all the parties receive the same output) when one third of the parties, or more, might be corrupted. Assuming all parties are connected via a peer-to-peer network, but no broadcast channel (nor a secure setup phase) is available, we prove the following characterization: * A symmetric n-party functionality can be securely computed facing n/3<=t<n/2 corruptions (i.e., honest majority), if and only if it is \emph{(n-2t)-dominated}; a functionality is k-dominated, if \emph{any} k-size subset of its input variables can be set to determine its output. * Assuming the existence of one-way functions, a symmetric n-party functionality can be securely computed facing t>=n/2 corruptions (i.e., no honest majority), if and only if it is 1-dominated and can be securely computed with broadcast. It follows that, in case a third of the parties might be corrupted, broadcast is necessary for securely computing non-dominated functionalities (in which "small" subsets of the inputs cannot determine the output), including, as interesting special cases, the Boolean XOR and coin-flipping functionalities.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2016
Keywords
broadcastpoint-to-point communicationmultiparty computationcoin flippingfairnessimpossibility result
Contact author(s)
cohenrb @ cs biu ac il
History
2017-08-29: last of 3 revisions
2015-09-02: received
See all versions
Short URL
https://ia.cr/2015/846
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.