ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

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.