Independence is a fundamental property needed to achieve security in fault-tolerant distributed computing. In practice, distributed communication networks are neither fully synchronous or fully asynchronous, but rather loosely synchronized. By this, we mean that in a communication protocol, messages at a given round may depend on messages from other players at the same round. These possible dependencies among messages create problems if we need n players to announce independently chosen values. This task is called simultaneous broadcast. In this paper, we present the first constant round protocol for simultaneous broadcast in a reasonable computation model (which includes a common shared random string among the players). The protocol is provably secure under general cryptographic assumptions. In the process, we develop a new and stronger formal definition for this problem. Previously known protocols for this task required either O(log n) or expected constant rounds to complete (depending on the computation model considered).
Independence is a fundamental property needed to achieve security in fault-tolerant distributed computing. In practice, distributed communication networks are neither fully synchronous or fully asynchronous, but rather loosely synchronized. By this, we mean that in a communication protocol, messages at a given round may depend on messages from other players at the same round. These possible dependencies among messages create problems if we need n players to announce independently chosen values. This task is called simultaneous broadcast. In this paper, we present the first constant round protocol for simultaneous broadcast in a reasonable computation model (which includes a common shared random string among the players). The protocol is provably secure under general cryptographic assumptions. In the process, we develop a new and stronger formal definition for this problem. Previously known protocols for this task required either O(log n) or expected constant rounds to complete (depending on the computation model considered).
Simultaneous broadcast [CGMAJ is a fundamental tool in designing secure protocols for fault tolerant distributed computing.A system that supports it enables n processes to globally commit to independently chosen values (a significantly harder task than mere agreement).It is also a basic building block in a recent %ompleteness" theorem of [GMWZ].In this paper we present a new protocol for simultaneous broadcast.Building upon past work, we introduce a novel method of concurrently alternating and interleaving n executions of verifiable secret sharing protocols.This approach greatly improves the time complexity (number of communication rounds) of simultaneous broadcast.Previous protocols (combination of [CGMA] and [GMW]) q re uired the complete serialization of the ra verifiable secret sharings, resulting in n(n) communication rounds.Our protocol is constructive, and requires only log n + log log n serial executions of verifiable secret sharings.It preserves maximum fault tolerance (t < n/2 faults), and polynomial resource bounds (internal computation and communication bits).The same improvement appiies to the general simulation in [GMWX].In light of its improved performance, it is significant that our our protocol has a fairly simple correctness proof.In the slippery business of distributed cryptographic protocols, simpler proofs are important.
Broadcast and verifiable secret sharing (VSS) are central building blocks for secure multi-party computation. These protocols are required to be resilient against a Byzantine adversary who controls at most t out of the n parties running the protocol. In this dissertation, we consider the design of fault-tolerant protocols for broadcast and verifiable secret sharing with stronger security guarantees and improved round complexity. Broadcast allows a party to send the same message to all parties, and all parties are assured they have received identical messages. Given a public-key infrastructure (PKI) and digital signatures, it is possible to construct broadcast protocols tolerating any number of corrupted parties. We address two important issues related to broadcast: (1) Almost all existing protocols do not distinguish between corrupted parties (who do not follow the protocol) and honest parties whose secret (signing) keys have been compromised (but who continue to behave honestly); (2) all existing protocols for broadcast are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. We propose new security models that capture these issues, and present tight feasibility and impossibility results. In the problem of verifiable secret sharing, there is a designated player who shares a secret during an initial sharing phase such that the secret is hidden from an adversary that corrupts at most t parties. In a subsequent reconstruction phase of the protocol, a unique secret, well-defined by the view of honest players in the sharing phase, is reconstructed. The round complexity of VSS protocols is a very important metric of their efficiency. We show two improvements regarding the round complexity of information-theoretic VSS. First, we construct an efficient perfectly secure VSS protocol tolerating t < n/3 corrupted parties that is simultaneously optimal in both the number of rounds and the number of invocations of broadcast. Second, we construct a statistically secure VSS protocol tolerating t < n/2 corrupted parties that has optimal round complexity, and an efficient statistical VSS protocol tolerating t < n/2 corrupted parties that requires one additional round.
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.
We present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system. [...] Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed. We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We [...] support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure. In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.
We present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system.
Communication is often the most significant bottleneck in distributed computing. Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed.
We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We develop a clear and concise set of definitions that support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure.
In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.
In a network of n players, each player i having private input zi, we show how the players can collaboratively evaluate a function f(zl, ..., zn) in a way that does not compromise the privacy of the players' inputs, and yet requires only a constant number of rounds of interaction.The underlying model of computation is a complete network of private channels, with broadcast, and a majority of the players must behave honestly.Our solution assumes the existence of a one-way function.share bi to player i.For some parameter t, t < n/2, we require that no t players get information about b from their pieces; and yet, b is recoverable, and is known to be recoverable, given the cooperation of the n -t good players--even if the t bad players try to obstruct b's recovery, or try to alter the recovered value.The value b which a player has effectively "committed to" is independent of the values that honest players may concurrently be committing to.After the sharing stage, a computation stage follows, in which each player, given his own shares of xl, ..., x,~, computes his own share of f(zt,..., z,~).To accomplish this, the function f to be evaluated is represented by a