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:

1) A symmetric $n$-party functionality can be securely computed facing
$n/3le t<n/2$ corruptions (ie 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 emph{determine} its
output.

2) Assuming the existence of one-way functions, a symmetric $n$-party
functionality can be securely computed facing $tge n/2$ corruptions (ie 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.

By admin