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 $3 t_{a} + 2 t_{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 $2 t_{a} + 2 t_{p} + t_{f} < n$ ; without broadcast, the additional condition $3 t_{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},
}