Most of this book has considered two-party and multiparty computation with security with (unfair) abort. This security notion allows the adversary to force the honest parties to abort even depending on the outputs of corrupted parties. (Note, however, that the adversary is not allowed to bias the output of honest parties in any other manner.) This relaxation of security is necessary if one wishes to tolerate arbitrarily many corruptions. A further relaxation considers computational security, where the adversary is assumed to be computationally bounded, e.g., probabilistic polynomial time. In this setting, any circuit can be securely realized even when arbitrarily many parties are corrupted, as long as one is willing to sacrifice fairness and robustness.
Most of this book has considered two-party and multiparty computation with security with (unfair) abort. This security notion allows the adversary to force the honest parties to abort even depending on the outputs of corrupted parties. (Note, however, that the adversary is not allowed to bias the output of honest parties in any other manner.) This relaxation of security is necessary if one wishes to tolerate arbitrarily many corruptions. A further relaxation considers computational security, where the adversary is assumed to be computationally bounded, e.g., probabilistic polynomial time. In this setting, any circuit can be securely realized even when arbitrarily many parties are corrupted, as long as one is willing to sacrifice fairness and robustness.
Most proposed protocols for multi-party computation are designed to be secure either against information-theoretic or against computational adversaries.Each setting has its known advantages and disadvantages.In the computational setting we can achieve nonrobust MPC for up to t < n corrupted parties, but relying on unproven intractability assumptions.In the information-theoretic setting we do not have any unproven assumptions, but only t < n/2 corrupted parties can be tolerated.In [Cha89] Chaum sketches a hybrid protocol that brings together the best of both worlds: Information-theoretic security with abort (i.e.privacy and correctness, but no fairness or robustness) is achieved for t < n/2 corrupted parties.Beyond this threshold, for t < n corrupted parties, the protocol achieves computational security with abort.In this work, we first formalize the protocol idea described in [Cha89] and prove its security.In a second step, we extend the protocol to provide fairness and robustness.Whereas fairness comes "for free", robustness requires a trade-off similar to the one in [IKLP06].Then, we describe a construction for realizing the protocol in the universallycomposable setting as proposed in [Can01].For his protocol, Chaum assumed that a broadcast channel is given.In the last part of this work we discuss the implications of dropping this assumption, and obtain an interesting new result: It is possible to achieve the same bounds as in [Cha89], extended with fairness, without a broadcast channel.
Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.
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.
Abstract. Most protocols for distributed, fault-tolerant computation, or multi-party computation (MPC), provide security guarantees in an all-or-nothing fashion: If the number of corrupted parties is below a certain threshold, these protocols provide all specified security guarantees. Beyond this threshold, they provide no security guarantees at all. Furthermore, most previous protocols achieve either information-theoretic (IT) security, in which case this threshold is low, or they achieve only computational security, in which case this threshold is high. In contrast, a hybrid-secure proto-col provides different security guarantees depending on the set of corrupted parties and the com-putational power of the adversary, without being aware of the actual adversarial setting. Thus, hybrid-secure MPC protocols allow for graceful degradation of security. We present a hybrid-secure MPC protocol that provides an optimal trade-off between IT robustness and computational privacy: For any robustness parameter ρ < n 2, we obtain one MPC protocol that is simultaneously IT secure with robustness for up to t ≤ ρ actively corrupted parties, IT secure with fairness (no robustness) for up to t < n 2, and computationally secure with agreement on abort
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 participating parties, and still preserves certain security guarantees. Most MPC protocols provide security guarantees in an all-or-nothing fashion: Either the set of corrupted parties is tolerated and the protocol provides all specified security guarantees, or the set of corrupted parties is not tolerated and the protocol provides no security guarantees at all. Similarly, corruptions are in an all-or-nothing fashion: Either a party is fully honest, or it is fully corrupted. For example, an actively secure protocol is rendered completely insecure when just one party is corrupted additionally to what is tolerated, even if all corrupted parties are only passive. 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