Most protocols for distributed, fault-tolerant computation, or multi-party computation (MPC), provide security guarantees in an all-or-nothing fashion. In contrast, a hybrid-secure protocol provides different security guarantees depending on the set of corrupted parties and the computational power of the adversary, without being aware of the actual adversarial setting. Thus, hybrid-secure MPC protocols allow for graceful degradation of security.
Most protocols for distributed, fault-tolerant computation, or multi-party computation (MPC), provide security guarantees in an all-or-nothing fashion. In contrast, a hybrid-secure protocol provides different security guarantees depending on the set of corrupted parties and the computational power of the adversary, without being aware of the actual adversarial setting. Thus, hybrid-secure MPC protocols allow for graceful degradation of security.
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
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.
Securemulti-party computation(MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set ofnmutually distrusting parties to carry out any joint computation of their private inputs, without disclosing any additional information about their inputs. MPC withinformation-theoreticsecurity (also calledunconditional security) provides the strongest security guarantees and remains secure even againstcomputationally unboundedadversaries.Perfectly-secureMPC protocols are a class of information-theoretically secure MPC protocols, which provide all the security guarantees in anerror-freefashion. The focus of this work is perfectly-secure MPC. Known protocols are designedassumingeither asynchronousorasynchronouscommunication network. It is well known that perfectly-securesynchronousMPC is possible as long as the adversary can corrupt anyts<n/3parties. On the other hand, perfectly-secureasynchronousMPC protocols can tolerate up tota<n/4corrupt parties. A natural question is does there exist asingleMPC protocol for the setting where the parties arenot awareof the exact network type and which can tolerate up tots<n/3corruptions in a synchronous network and up tota<n/4corruptions in anasynchronousnetwork. We design such abest-of-both-worldsperfectly-secure MPC protocol, provided3ts+ta<nholds. For designing our protocol, we design two important building blocks which are of independent interest. The first building block is a best-of-both-worldsByzantine agreement(BA) protocol toleratingt<n/3corruptions which remains securebothin a synchronous as well as asynchronous network. The second building block is a polynomial-based best-of-both-worldsverifiable secret-sharing(VSS) protocol, which can tolerate up totsandtacorruptions in asynchronousand in anasynchronousnetwork respectively.
In this dissertation, we consider the design of broadcast and secure multi-party computation (MPC) protocols in the presence of adversarial faults.
Secure multi-party computation is the most generic problem in fault-tolerant distributed computing. In principle, a multi-party computation protocol can be used to solve any distributed cryptographic problem. Informally, the problem of multi-party computation is the following: suppose we have n parties P1, P2,…, Pn where each party Pi has a private input xi. Together, the parties want to compute a function of their inputs (y1, y2,…, yn) = f(x1,x2,…, xn). However, some parties can be corrupted and do not execute a prescribed protocol faithfully. Even worse, they may be controlled by an adversary and attack the protocol in a coordinated manner. Despite the presence of such an adversary, a secure MPC protocol should ensure that each (corrupted) party Pi learn only its output yi but nothing more.
Broadcast in the presence of adversarial faults is one of the simplest special cases of multi-party computation and important component of larger protocols. In short, broadcast allows a party to send the same message to all parties, and all parties to be assured they have received identical messages.
The contribution of this dissertation is twofold. First, we construct broadcast and secure multi-party computation protocols for honest majority in a point-to-point network whose round complexities improve significantly upon prior work. In particular, we give the first expected constant-round authenticated broadcast protocol for honest majority assuming only public-key infrastructure and signatures. Second, we initiate the study of broadcast in radio networks in the presence of adversarial faults. In radio networks, parties communicate through multicasting messages; a message can only be received by the parties within some radius from the sender. Feasibility and impossibility results are given, and our bounds are tight.
Secure Multiparty Computation (MPC) is an expression encompassing cryptographic techniques that allow mutually distrustful parties to jointly perform computations over private data, ensuring correctness and preserving privacy despite malicious behavior. Guaranteed output is the strongest security goal for MPC: protocols with this property always deliver results. This is in contrast with weaker notions that allow malicious aborts. The seminal works of Ben-Or, Goldwasser, and Wigderson (STOC’88) and Rabin and Ben-Or (STOC’89) showed interactive protocols to compute any function with guaranteed output and perfect security if fewer than one third of parties are corrupted, or with statistical security (with a small error probability) if fewer than half are corrupted. These results hold when the set of participants is fixed throughout the execution. Ostrovsky and Yung’s proactive model (PODC’91) relaxes this assumption by allowing the set of corrupted parties to evolve over time, better capturing the dynamics of long-lived computations, where machines may be periodically compromised and recovered. The recent YOSO (You Only Speak Once) and fluid MPC models (CRYPTO’21) push this ambitious modelling even further by allowing for fully dynamic participation, with parties joining and leaving the computation at will. In this setting, known protocols with guaranteed output fall short of optimal resilience or rely on non-standard communication and adversarial assumptions. Matching the classical BGW and Rabin–Ben-Or bounds in these settings remained an open problem. We resolve these questions within the Layered MPC abstraction of David et al. (CRYPTO’23), in which the interaction pattern of a protocol is restricted to be a layered graph, meaning parties are partitioned into a sequence of disjoint sets (layers) and can send private and broadcast messages to parties in immediately subsequent layers. We match the BGW and Rabin and Ben-Or bounds in this model, fully characterizing the feasibility landscape of Layered MPC with guaranteed output. As a stepping stone towards our statistically secure protocol, we construct a more efficient and conceptually simpler computationally secure protocol relying on linear non-interactive commitments. Our results yield optimally-resilient and maximally-proactive MPC protocols with guaranteed output for both perfect and statistical security.