. 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 ta players and, additionally, can passively corrupt (i.e. read the entire information of) up to tp players and fail-corrupt (i.e. stop the computation of) up to tf other players. The classical results in multi-party computation are for the special cases of only passive (ta = tf = 0) or only active (tp = tf = 0) corruption. In the passive case, every function can be computed securely if and only if tp ! n=2. In the active case, every function can be computed securely if and only if ta ! n=3; when a broadcast channel is available, then this bound is ta ! n=2. These bounds are tight. Strictly improving these results, one of our results states that, in addition to tolerating ta ! n=3 actively corrupted players, pr...
. 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 ta players and, additionally, can passively corrupt (i.e. read the entire information of) up to tp players and fail-corrupt (i.e. stop the computation of) up to tf other players. The classical results in multi-party computation are for the special cases of only passive (ta = tf = 0) or only active (tp = tf = 0) corruption. In the passive case, every function can be computed securely if and only if tp ! n=2. In the active case, every function can be computed securely if and only if ta ! n=3; when a broadcast channel is available, then this bound is ta ! n=2. These bounds are tight. Strictly improving these results, one of our results states that, in addition to tolerating ta ! n=3 actively corrupted players, pr...
This paper improves on the classical results in uncondition- ally secure multi-party computation among a set of n players, by consid- ering a model with three simultaneously occurring types of player cor- ruption: the adversary can actively corrupt (i.e. take full control over) up to ta players and, additionally, can passively corrupt (i.e. read the entire information of) up to tp players and fail-corrupt (i.e. stop the compu- tation of) up to tf other players. The classical results in multi-party computation are for the special cases of only passive (ta = tf =0 ) or only active (tp = tf = 0) corruption. In the passive case, every function can be computed securely if and only if tp <n = 2. In the active case, every function can be computed securely if and only if ta <n =3; when a broadcast channel is available, then this bound is ta <n =2. These bounds are tight. Strictly improving these results, one of our results states that, in addi- tion to tolerating ta <n =3 actively corrupted players, privacy can be guaranteed against every minority, thus tolerating additional tp 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 ta, tp and tf for four scenarios. Zero failure probability is achievable if and only if 3ta +2 tp + tf <n ; this holds whether or not a broadcast chan- nel is available. Exponentially small failure probability with a broadcast channel is achievable if and only if 2ta +2 tp +tf <n ; without broadcast, the additional condition 3ta + tf <n is necessary and sucient. In this corrected version, an error pointed out by Damg ard (Dam99) is corrected.
The classical results in unconditional multi-party computation among a set of n players state that less than n/2 passive or Iess than n/3 active adversaries can be tolerated; assuming a broadcast channel the threshold for active adversaries is ta/2.Strictly generalizing these results we specify the set of potential y misbehaving players as an arbitrary set of subsets of the player set.We prove the necessary and sufficient conditions for the existence of secure multi-party protocols in terms of the potentially misbehaving player sets.For every function there exists a protocol secure against a set of potential passive collusions if and only if no two of these collusions add up to the full player set.The same condition applies for active adversaries when assuming a broadcast chzmnel.Without broadcast channels, for every function there exists a protocol secure against a set of potential active adverse player sets if and only if no three of these sets add up to the full player set.The complexities of the protocols not using a broadcast channel are polynomial, that of the protocol with broadcast is only slightly higher.
In secure multi-party computation n parties jointly evaluate an n-variate function f in the presence of an adversary which can corrupt up till t parties. Almost all the works that have appeared in the literature so far assume the presence of authenticated channels between the parties. This assumption is far from realistic. Two directions of research have been borne from relaxing this (strong) assumption: (a) The adversary is virtually omnipotent and can control all the communication channels in the network, (b) Only a partially connected topology of authenticated channels is guaranteed and adversary controls a subset of the communication channels in the network. This work introduces a new setting for (unconditional) secure multiparty computation problem which is an interesting intermediate model with respect to the above well studied models from the literature (by sharing a salient feature from both the above models). We consider the problem of (unconditional) secure multi-party computation when 'some' of the communication channels connecting the parties can be corrupted passively as well as actively. For this setting, some honest parties may be connected to several other honest parties via corrupted channels and may not be able to authentically communicate with them. Such parties may not be assured the canonical guarantees of correctness or privacy. We present refined definitions of security for this new intermediate model of unconditional multiparty computation. We show how to adapt protocols for (Unconditional) secure multiparty computation to realize the definitions and also argue the tightness of the results achieved by us.
Abstract. The goal of Multi-Party Computation (MPC) is to perform an arbitrary computation in a distributed, private, and fault-tolerant way. For this purpose, a fixed set of n parties runs a protocol that tolerates an adversary corrupting a subset of the parties, preserving certain security guarantees like correctness, secrecy, robustness, and fairness. Corruptions can be either passive or active: A passively corrupted party follows the protocol correctly, but the adversary learns the entire internal state of this party. An actively corrupted party is completely controlled by the adversary, and may deviate arbitrarily from the protocol. A mixed adversary may at the same time corrupt some parties actively and some additional parties passively. In this work, we consider the statistical setting with mixed adversaries and study the exact consequences of active and passive corruptions on secrecy, correctness, robustness, and fairness separately (i.e., hybrid security). Clearly, the number of passive corruptions affects the thresholds for secrecy, while the number of active corruptions affects all thresholds. It turns out that in the statistical setting, the number of passive corruptions in particular also affects the threshold for correctness, i.e., in all protocols there are (tolerated) adversaries for which a single additional passive corruption is sufficient to break correctness. This is in contrast to both the perfect and the computational setting, where such an influence cannot be observed. Apparently, this effect arises from the use of information-theoretic signatures, which are part of most (if not all) statistical protocols.
Two types of generalizations in secure multi-party computation are described. First, we report on a new general adversary model: while previous protocols were designed to tolerate misbehavior of one of two types (active or passive adversaries) the new protocols tolerate mixed types of adversaries, i.e. an adversary that can corrupt players actively, passively, or can let them crash (i.e. stop execution). We derive the necessary and sufficient conditions under which such a general adversary can be tolerated. Second, we present a generic protocol framework that unifies previous approaches achieving unconditional (or information-theoretic) security and cryptographic security (i.e. security based on a cryptographic intractability assumption). This is achieved by introducing secret sharing schemes with an additional property called the multiplication property and a new type of homomorphic commitment scheme, and by generalizing the concept of commitments.
The goal of Multi-Party Computation (MPC) is to perform an arbitrary computation in a distributed, private, and fault-tolerant way. For this purpose, a fixed set of n parties runs a protocol that tolerates an adversary corrupting a subset of the participating parties, and still preserves certain security guarantees.
Most MPC protocols provide security guarantees in an all-or-nothing fashion. In this paper, we provide the first treatment of MPC with graceful degradation of both security and corruptions. First of all, our protocols provide graceful degradation of security, i.e., different security guarantees depending on the actual number of corrupted parties: the more corruptions, the weaker the security guarantee. We consider all security properties generally discussed in the literature (secrecy, correctness, robustness, fairness, and agreement on abort). Furthermore, the protocols provide graceful degradation with respect to the corruption type, by distinguishing fully honest parties, passively corrupted parties, and actively corrupted parties. Security can be maintained against more passive corruptions than is possible for active corruptions.
We focus on perfect security, and prove exact bounds for which MPC with graceful degradation of security and corruptions is possible for both threshold and general adversaries. Furthermore, we provide protocols that meet these bounds. This strictly generalizes known results on hybrid security and mixed adversaries.