# Trading Correctness for Privacy in Unconditional Multi-Party Computation

## Matthias Fitzi and Martin Hirt and Ueli Maurer

```
```This paper improves on the classical results in unconditionally secure
multi-party computation among a set of $n$ players, by considering a model
with three simultaneously occurring types of player corruption: the
adversary can actively corrupt (i.e. take full control over) up to $t_a$
players and, additionally, can passively corrupt (i.e. read the entire
information of) up to $t_p$ players and fail-corrupt (i.e. stop the
computation of) up to $t_f$ other players. The classical results in
multi-party computation are for the special cases of only passive
($t_a=t_f=0$) or only active ($t_p=t_f=0$) corruption. In the passive case,
every function can be computed securely if and only if $t_p<n/2$. In the
active case, every function can be computed securely if and only if
$t_a<n/3$; when a broadcast channel is available, then this bound is
$t_a<n/2$. These bounds are tight.

Strictly improving these results, one of our results states that, in
addition to tolerating $t_a<n/3$ actively corrupted players, privacy can be
guaranteed against every minority, thus tolerating * additional*}
$t_p\leq n/6$ passively corrupted players. These protocols require no
broadcast and have an exponentially small failure probability. We further
show that the bound $t<n/2$ for passive corruption holds even if the
adversary is additionally allowed to make the passively corrupted players
fail.

Moreover, we characterize completely the achievable thresholds $t_a$, $t_p$
and $t_f$ for four scenarios. Zero failure probability is achievable if and
only if $3t_{a}+2t_{p}+t_{f} < n$; this holds whether or not a broadcast
channel is available. Exponentially small failure probability with a
broadcast channel is achievable if and only if $2t_{a}+2t_{p}+t_{f}<n$;
without broadcast, the additional condition $3t_{a}+t_{f}<n$ is necessary
and sufficient.

In this corrected version, an error pointed out by Damg{å}rd
\cite{Damgaa99:TRman} is corrected.