01302842

a

01302842 Fitzi, Matthias Hirt, Martin Maurer, Ueli Trading correctness for privacy in unconditional multi-party computation. (Extended abstract). Krawczyk, Hugo (ed.), Advances in cryptology - CRYPTO '98. 18th annual international cryptology conference, Santa Barbara, CA, USA, August 23-27, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1462, 121-136 (1998). 1998 Berlin: Springer EN multi-party computation Summary: 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\le n/6$ passively corrupted players. These protocols require no broadcast and have an exponentially small failure probability. When zero failure probability is required, privacy can be maintained against any minority, but one can even tolerate $t_a< n/4$ of these players to be corrupted actively. 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 $2t_a+ 2t_p+ t_f< n$ and $3t_a+ 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 $2t_a+ 2t_p+ t_f< n$; without broadcast, the additional condition $3t_a+ t_f< n$ is necessary and sufficient.