Trading Correctness for Privacy in Unconditional Multi-Party Computation
Matthias Fitzi, 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.
BibTeX Citation
@inproceedings{FiHiMa98,
author = {Matthias Fitzi and Martin Hirt and Ueli Maurer},
title = {Trading Correctness for Privacy in Unconditional Multi-Party Computation},
editor = {Hugo Krawczyk},
booktitle = {Advances in Cryptology --- CRYPTO~'98},
pages = 121--136,
series = {Lecture Notes in Computer Science},
volume = 1462,
year = 1998,
month = 8,
note = {Corrected proceedings version},
publisher = {Springer-Verlag},
}