# Complete Characterization of Adversaries Tolerable in Secure Multi-Party Computation

## Martin Hirt and Ueli Maurer

```
```The classical results in unconditional multi-party computation among a
set of $n$ players state that less than $n/2$ passive or less than $n/3$
active adversaries can be tolerated; assuming a broadcast channel the
threshold for active adversaries is $n/2$. Strictly generalizing these
results we specify the set of potentially misbehaving players as an
arbitrary set of subsets of the player set. We prove the necessary and
sufficient conditions for the existence of secure multi-party protocols
in terms of the potentially misbehaving player sets.

For every function there exists a protocol secure against a set of
potential passive collusions if and only if no two of these collusions
add up to the full player set. The same condition applies for active
adversaries when assuming a broadcast channel. Without broadcast
channels, for every function there exists a protocol secure against a set
of potential active adverse player sets if and only if no three of these
sets add up to the full player set.

The complexities of the protocols not using a broadcast channel are
polynomial, that of the protocol with broadcast is only slightly higher.