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 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
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).
Verifiable secret sharing (VSS) is a fundamental cryptographic primitive, lying at the core of secure multi-party computation (MPC) and, as the distributed analogue of a commitment functionality, used in numerous applications. In this paper we focus on unconditionally secure VSS protocols with honest majority. In this setting it is typically assumed that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Because broadcast cannot be simulated on a point-to-point network when a third or more of the parties are corrupt, it is impossible to construct VSS (and more generally, 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 VSS, primarily in terms of round complexity. In this work we consider a refinement of the round complexity of VSS, by adding a measure we term broadcast complexity. We view the broadcast channel as an expensive resource and seek to minimize the number of rounds in which it is invoked as well. We construct a (linear) VSS protocol which uses the broadcast channel only twice in the sharing phase, while running in an overall constant number of rounds. 1
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.
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.
Secure Multi-Party Computation (MPC) with small number of parties is an interesting area of research, primarily due to its ability to model most real-life MPC applications and the simplicity and efficiency of the resulting protocols. In this work, we present efficient, constant-round 3-party (3PC) and 4-party (4PC) protocols in the honest-majority setting that achieve strong security notions of fairness (corrupted parties receive their output only if all honest parties receive output) and guaranteed output delivery (corrupted parties cannot prevent honest parties from receiving their output). Being constant-round, our constructions are suitable for Internet-like high-latency networks and are built from garbled circuits (GC). Assuming the minimal model of pairwise-private channels, we present two protocols that involve computation and communication of a single GC-- (a) a 4-round 3PC with fairness, (b) a 5-round 4PC with guaranteed output delivery. Empirically, our protocols are on par with the best known 3PC protocol of Mohassel et al. [CCS 2015] that only achieves security with selective abort, in terms of the computation time, LAN runtime, WAN runtime and communication cost. In fact, our 4PC outperforms the 3PC of Mohassel et al. significantly in terms of per-party computation and communication cost. With an extra GC, we improve the round complexity of our 4PC to four rounds. The only 4PC in our setting, given by Ishai et al. [CRYPTO 2015], involves 12 GCs. Assuming an additional broadcast channel, we present a 5-round 3PC with guaranteed output delivery that involves computation and communication of a single GC. A broadcast channel is inevitable in this setting for achieving guaranteed output delivery, owing to an impossibility result in the literature. The overall broadcast communication of our protocol is nominal and most importantly, is independent of the circuit size. This protocol too induces a nominal overhead compared to the protocol of Mohassel et al.
In the setting of secure multiparty computation, several distrustful parties wish to carry out a distributed computing task on their local private data while satisfying several security properties such as correctness, privacy, independence of inputs and fairness. The aim of secure multiparty computation (MPC) is to enable the parties to carry out the computation in a secure manner, eliminating any attempt of an adversarial entity to harm the execution. The concept of secure computation is very general and fundamental in cryptography, and models any distributed computing task, including simple computations as coin-tossing and broadcast, as well as more complex tasks such as electronic auctions and anonymous transactions. In this thesis, we study two foundational aspects of secure computation: perfect security and fairness. In the first part of this thesis, we study perfect security in secure computation. A protocol that is perfectly secure cannot be broken even when the adversary has unlimited computational power and its security holds unconditionally. One of the most fundamental results of secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. When the adversary is semi-honest this holds as long as t < n/2 parties are corrupted, and when the adversary is malicious this holds as long as t < n/3 parties are corrupted. Unfortunately, a full proof of these results was never published. In this thesis, we remedy this situation and provide a full proof of security of the BGW protocol. This also includes a full description of the protocol for the malicious setting. In addition to the above, we observe that by some simple and natural modifications, the BGW protocol can be significantly simplified and one of its expensive (and perhaps most complicated) subprotocols can be saved. We present a new multiplication protocol that is based on the original construction, but is simpler and achieves higher efficiency. In the second part of this thesis, we study fairness in secure two party computation. Informally, the fairness property guarantees that if one party receives its output, then the other party does too. The well-known impossibility result of Cleve (STOC 1986) implies that, in general, it is impossible to securely compute a function with complete fairness without an honest majority. Until recently, the accepted belief has been that nothing non-trivial can be computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist some non-trivial (deterministic, finite-domain) Boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. We focus on this question and give both positive and negative results. We first characterize