Information Security and Cryptography Research Group

Trading Correctness for Privacy in Unconditional Multi-Party Computation

Matthias Fitzi, Martin Hirt, and Ueli Maurer

Advances in Cryptology — CRYPTO '98, Lecture Notes in Computer Science, Springer-Verlag, vol. 1462, pp. 121–136, Aug 1998, Corrected proceedings version.

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

    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},

Files and Links