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. 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
We consider the situation where a large number n of players want to securely compute a large function f with security against an adaptive, malicious adversary which might corrupt t<cn of the parties for some given c∈[0,1) . In other words, only some arbitrarily small constant fraction of the parties are assumed to be honest. For any fixed c, we consider the asymptotic complexity as n and the size of f grows. We are in particular interested in the computational overhead, defined as the total computational complexity of all parties divided by the size of f. We show that it is possible to achieve poly-logarithmic computational overhead for all c<1 . Prior to our result it was only known how to get poly-logarithmic overhead for c<21 . We therefore significantly extend the area where we can do secure multiparty computation with poly-logarithmic overhead. Since we allow that more than half the parties are corrupted, we can only get security with abort, i.e., the adversary might make the protocol abort before all parties learn their outputs. We can, however, for all c make a protocol for which there exists d>0 such that if at most dn parties are actually corrupted in a given execution, then the protocol will not abort. Our result is solely of theoretical interest. In its current form, it has not practical implications whatsoever.