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.
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 perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource
Secure Multi-party Computation (MPC) considers the problem where a set of mutually distrusting parties want to jointly compute a function over their private inputs, without revealing any extra information about these inputs other than what it can be inferred from the output of the function. This setting is well-motivated, and it has many real-world applications such as auction, voting, etc. MPC can be also seen as a generalization of many natural cryptographic primitives. For example, zero-knowledge (ZK) can be viewed as a special case of two-party secure computation. In ZK, a party, called prover aims to convince a second party, called verifier, that the prover’s private input witness w and a public input statement x belong to a relation R. An important research direction in secure computation is to find the trade-off between the required setup (e.g., the use of the broadcast channel, the use of common reference string (CRS) / public key infrastructure (PKI), the upper bound of the parties that can be corrupted, etc.), and the security guarantees that can be achieved. The setups can be viewed as some general assumptions that the protocol needs to satisfy, and they influence the usability of the protocol in real-world scenarios. In principle, having simpler (or no) setups mean that the protocol is more general and can be more useful in real-world scenarios. At the same time, having simpler setups may lead to weaker security guarantees. Therefore, finding the trade-off between setup and security guarantees is important and meaningful. In this thesis, we target MPC and ZK, and we focus on how to minimize the setup for MPC and ZK while still providing meaningful levels of security. More specifically: Regarding MPC, we focus on the dishonest majority (i.e., the adversary can corrupt all but one party), and we aim at 1) minimizing the use of broadcast channels. 2) studying the MPC with pre-processing when no setup is available. • Informally, a broadcast channel guarantees that when a message is sent, this reaches all the parties, without ambiguity. It also guarantees that if an honest party receives a message from a corrupted party, then it is guaranteed that all the honest parties have received the message. To realize broadcast, parties in the protocol could run the broadcast protocol, which may require many rounds of peer-to-peer communications. An alternative way is to rely on physical or external infrastructure such as blockchain. In both cases, broadcast is expensive, as such, we want to minimize its use. In particular, this thesis presents the following results: – When assuming no setup, we give a complete characterization with respect to the use of broadcast channels, and we obtain the optimal results. – We consider the same problem for the case that we only want to allow the black-box use (i.e., do not have access to the code of the algorithm) of the oblivious transfer protocol. We also give a characterization. • In the standard definition of MPC, the parties’ private inputs are fixed before the start of the protocol. However, there is another type of MPC named MPC with pre-processing, where the protocol can pre-compute some messages without using parties’ inputs, and these messages can accelerate computations in the online phase (i.e., other computations that require parties’ inputs). Since some expensive computations can be pre-computed, the online phase could be more lightweight. Therefore, we want to remove the dependency of the input from as many rounds as possible, so that we can do some pre-processing. In this direction, we explore the protocol with no setup. We provide a compiler that can turn a big class of MPC protocol that may require the inputs already to compute the first round, into a new protocol that needs the inputs only in the last two rounds. We also propose new MPC definitions that capture this delayed-input features. Regarding ZK, we do the following: • In standard single-theorem ZK definition, the security of the ZK protocol is guaranteed to hold only when one proof is issued. In the case where multiple zero-knowledge proofs need to be issued (i.e., to prove multiple NP statements), each new zero-knowledge proof requires a freshly generated setup. In the multi-theorem ZK definition, instead, one setup is sufficient for generating multiple zero-knowledge proofs for multiple instances. We propose a multi-theorem protocol (in the format of a compiler) that follows the Fiat-Shamir paradigm and relies on correlation intractable hash functions. Moreover, our protocol remains zero-knowledge and sound even against adversaries that choose the statement to be proven (and the witness for the case of zero-knowledge) adaptively on the key of the hash function. Prior works could achieve this adaptive security only inefficiently via NP reductions. • ZK protocols are secure only when all setups are correctly generated, but in real-world scenarios, some of the setups may not be correctly generated. For instance, to run a non-interactive zero-knowledge (NIZK) protocol, the setup CRS could be chosen with bias. In this case, the security of the NIZK protocol does not hold anymore. Instead of finding a secure ZK candidate, one alternative solution is to have multiple instantiations of ZK candidates and assume that only for a subset of them the setup is generated correctly. More formally, we consider the case where only a subset of the instances are secure. In more detail, given access to n candidate instantiations of a NIZK for some language, we want to have a construction that itself implements a NIZK for the same language without relying on any additional computational assumptions. We refer to this type of construction as combiner, and the combiner is secure assuming at least t of the given candidates are secure. In this work, we provide three different constructions of robust NIZK combiners and show that combiners are impossible to realize unless the majority of the input candidates are secure.
Abstract. A broadcast protocol allows a sender to distribute a message through a point-to-point network to a set of parties, such that (i) all parties receive the same message, even if the sender is corrupted, and (ii) this is the sender’s message, if he is honest. Broadcast protocols satisfying these properties are known to exist if and only if t < n/3, where n denotes the total number of parties, and t denotes the maximal number of corruptions. When a setup allowing signatures is available to the parties, then such protocols exist even for t < n. Broadcast is the probably most fundamental primitive in distributed cryptography, and is used in almost any cryptographic (multi-party) protocol. However, a broadcast protocol “only ” satisfying the above properties might be insecure when being used in the context of another protocol. In order to be safely usable within other protocols, a broadcast protocol must satisfy a simulation-based security notion, which is secure under composition. In this work, we show that most broadcast protocols in the literature do not satisfy a (natural) simulation-based security notion. We do not know of any broadcast protocol which could be securely invoked in a multi-party computation protocol in the secure-channels model. The problem is that existing protocols for broadcast do not preserve the secrecy of the message while being broadcasted, and in particular allow the adversary to corrupt the sender (and change the message), depending on the message being broadcasted. For example, when every party should broadcast a random bit, the adversary could corrupt those parties that want to broadcast 0, and make them broadcast 1. More concretely, we show that simulatable broadcast in a model with secure channels is possible if and only if t < n/3, respectively t ≤ n/2 when a signature setup is available. The positive results are proven by constructing secure broadcast protocols.
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.
Multiparty computation (MPC) is a powerful and generic cryptographic framework capable of realizing essentially any cryptographic task (functionality) while preserving privacy and robustness. In the MPC model, a group of mutually distrustful parties seek to jointly compute a function f of their privately held inputs x1, ..., xn, while revealing no information about those inputs beyond what is entailed by the function output(s). Some portion of these players may be corrupted, controlled by a centralized adversary who directs their (mis)behavior and seeks to gain information on private inputs or to disrupt the protocol execution.
In this work, we examine the resource requirements of information-theoretically secure multiparty computation. In particular, we look at trade-offs involving what we call assumptions, by which we mean two aspects of the model's setup: (1) the extent to which parties are connected by secure, pairwise communication channels; and (2) the usage (as a black box) of a channel—a primitive which enforces consistency among views by allowing a single party to send a message to all other parties which is guaranteed to be consistent, even if the broadcaster is corrupted.
Part I of this work focuses on the first network-model assumption, that of the graph's connectivity by pairwise channels. We show upper and lower bounds on communication complexity in the Secure Message Transmission with Public Discussion (SMT-PD) model, as a function of the threshold of corrupted parties. The SMT-PD model, which abstracts the problem of secure communication over a partially connected network, includes two components: a public and a set of simple channels. We show significant improvements in both areas: on the channel, we reduce communication to logarithmic in terms of the message's bit-length m, where the previous best result was linear in m; on the simple channels, we reduce from O(mn) to O(mn/(n−t)), where n is the number of simple channels and t is a bound on the number of corrupted channels. Using tools from information theory, we show this amount of simple-wire communication is essentially optimal. Finally, we give an amortized solution which drastically improves communication over channel when the protocol is repeated many times sequentially.
Part II shifts focus to the second network-model assumption, the use of an atomic broadcast primitive. Here we show that three broadcast rounds suffice for general secure computation, while two broadcast rounds are necessary. In particular we show that even for the natural and important functionality of Weak Secret Sharing—a type of distributed commitment—there is no protocol which uses only a single broadcast and achieves better than an explicit constant probability of success (so the protocol's success cannot be a function of a security parameter).
Secure multi-party computation (MPC) enables distrustful parties to jointly perform computations while guaranteeing both the privacy of their inputs and the correctness of the computation.
This thesis explores two aspects of secure multi-party computation: adaptive security and round efficiency. Adaptive security is concerned with an adversary that adaptively determines who and when to corrupt during the course of the computation. Even though this is a very natural and realistic assumption about the adversary, most of the MPC literature addresses security only against a static adversary — an adversary that chooses (and fixes) which parties to corrupt before the protocol starts executing. A protocol is called round-efficient if it runs in a small number of rounds. Constructing such protocols is important since efficiency of a protocol is greatly influenced by its round complexity.
The security in this thesis is formulated in the universal composability (UC) framework introduced by Canetti [Can01]. Protocols secure in the UC framework remain secure even when executed concurrently with other arbitrary protocols running in some larger network, and can be used as subroutines of larger protocols in a modular fashion. This property is important considering that nowadays many protocols are executed concurrently with others in the Internet.
With the focus on adaptive security and round efficiency, we obtain the following results:
(1) We show that with access to an ideal commitment functionality, there exists a protocol that UC realizes any well-formed multi-party functionality against a malicious, adaptive adversary that may corrupt any number of parties, with black-box access to any protocol that UC realizes oblivious transfer against a semi-honest, adaptive adversary.
(2) We show that there exists a protocol that UC realizes oblivious transfer against a semi-honest, adaptive adversary, with black-box access to a cryptographic primitive called a trapdoor simulatable cryptosystem, which is a natural relaxation of a simulatable cryptosystem introduced by Damgard and Nielsen [3N00].
We also show that the primitive can be constructed based on hardness of factoring.
(3) We present a single-message protocol that UC realizes two-party computing with encrypted data (a variant of secure two-party computation), based on the DDH assumption and non- interactive zero-knowledge arguments. The protocol achieves security against a malicious, static adversary.
(4) We present two round-efficient protocols that UC realize multi-party computing with encrypted data (a variant of secure multi-party computation), based on the DDH assumption and non-interactive zero-knowledge arguments. The first (resp. second) protocol requires one round (resp. two rounds) with appropriate preprocessing, which is independent of the exact circuit and actual inputs of the specific instance problem to solve — only the bound on the circuit size is known. Although the first protocol is more round-efficient, the preprocessing of the second is sometimes better under some efficiency considerations. Both protocols achieve security against a malicious, static adversary that may corrupt up to all but one parties.