Secure multi-party computation (MPC) is a central problem in cryptography. Unfortunately, it is well known that MPC is possible if and only if the underlying communication network has very large connectivity—specifically, (t), wheretis the number of potential corruptions in the network. This impossibility result renders existing MPC results far less applicable in practice, since most deployed networks have in fact a very small degree. In this paper, we show how to circumvent this impossibility result and achieve meaningful security guarantees for graphs with small degree (such as expander graphs and several other topologies). In fact, the notion we introduce, which we call almost-everywhere MPC, building on the notion of almost-everywhere agreement due to Dwork, Peleg, Pippenger and Upfal, allows the degree of the network to be much smaller than the total number of allowed corruptions. In essence, our definition allows the adversary to implicitly wiretap some of the good nodes by corrupting sufficiently many nodes in the “neighborhood ” of those nodes. We show protocols that satisfy our new definition, retaining both correctness and privacy for most nodes despite small connectivity, no matter how the adversary chooses his corruptions. Instrumental in our constructions is a new model and protocol for the secure message transmission (SMT) problem, which we call SMT by public discussion, and which we use for the establishment of pairwise secure channels in limited connectivity networks. Key words: Secure multi-party computation, almost-everywhere agreement, secure message transmission, expander graphs, bounded-degree networks. 1
Secure multi-party computation (MPC) is a central problem in cryptography. Unfortunately, it is well known that MPC is possible if and only if the underlying communication network has very large connectivity—specifically, (t), wheretis the number of potential corruptions in the network. This impossibility result renders existing MPC results far less applicable in practice, since most deployed networks have in fact a very small degree. In this paper, we show how to circumvent this impossibility result and achieve meaningful security guarantees for graphs with small degree (such as expander graphs and several other topologies). In fact, the notion we introduce, which we call almost-everywhere MPC, building on the notion of almost-everywhere agreement due to Dwork, Peleg, Pippenger and Upfal, allows the degree of the network to be much smaller than the total number of allowed corruptions. In essence, our definition allows the adversary to implicitly wiretap some of the good nodes by corrupting sufficiently many nodes in the “neighborhood ” of those nodes. We show protocols that satisfy our new definition, retaining both correctness and privacy for most nodes despite small connectivity, no matter how the adversary chooses his corruptions. Instrumental in our constructions is a new model and protocol for the secure message transmission (SMT) problem, which we call SMT by public discussion, and which we use for the establishment of pairwise secure channels in limited connectivity networks. Key words: Secure multi-party computation, almost-everywhere agreement, secure message transmission, expander graphs, bounded-degree networks. 1
Secure multiparty computation of a multivariate function is a central problem in cryptography. It is well known that secure multiparty computation can be realized by a set of n parties iff the connectivity of the underlying (authenticated) communication network is more than twice the number of corrupted parties. This impossibility result makes secure multiparty computation far less applicable in practice, as most deployed networks have a degree much lower than O(n) and one would ideally like to be able to tolerate Θ(n) corrupted parties. In this work we consider a recently proposed model for (Unconditional) secure multiparty computation for networks of low degrees for which authenticated channels are available only between very few pairs of parties. Not all honest parties may be expected to achieve traditional security guarantees of multiparty computation for this model because of theoretical limitations posed by lack of infrastructure. Honest parties which are not given canonical guarantees of Correctness and Privacy are called ”sacrificed” and the resulting notion is called almost everywhere secure computation. In this conceptual note, we investigate the previous results about this model by Garay and Ostrovsky'2008. We explain why these results hold only for weak honest-but-curious type passive corruptions. We emphasize why the results for almost everywhere secure computation are theoretically interesting and practically relevant only when active malicious corruptions are allowed. We argue the limitation of hybrid argument for realizing privacy property when Byzantine corruptions are allowed. From this we deduce that simulation based reduction approach is necessary to realize even input indistinguishability type definition of privacy for the stand alone setting. We present a conceptual exposition of the simulator based approach for defining privacy of a.e.s.c. Finally, we present a brief overview of technicalities involved in realizing a.e.s.c. when malicious corruptions are allowed.
Most existing work on secure multi-party computation (MPC) ignores a key idiosyncrasy of modern communication networks, that there are a limited number of communication paths between any two nodes, many of which might even be corrupted. The problem becomes particularly acute in the information-theoretic setting, where the lack of trusted setups (and the cryptographic primitives they enable) makes communication over sparse networks more challenging. The work by Garay and Ostrovsky [EUROCRYPT’08] on almost-everywhere MPC (AE-MPC), introduced “best-possible security” properties for MPC over such incomplete networks, where necessarily some of the honest parties may be excluded from the computation. In this work, we provide a universally composable definition of almost-everywhere security , which allows us to automatically and accurately capture the guarantees of AE-MPC (as well as AE-communication, the analogous “best-possible security” version of secure communication) in the Universal Composability (UC) framework of Canetti. Our results offer the first simulation-based treatment of this important but under-investigated problem, along with the first simulation-based proof of AE-MPC. To achieve that goal, we state and prove a general composition theorem, which makes precise the level or “quality” of AE-security that is obtained when a protocol’s hybrids are replaced with almost-everywhere components.
Secure multi-party computation (MPC) is one of the most important primitives in cryptography. Several directions to construct and improve MPC protocols have been studied over the past decades. The majority of existing MPC protocols rely on assumptions such as every party communicates with every other party or every party needs to know every other party and the computation algorithm well in advance. Such assumptions can be difficult to achieve in modern large scale networks. This thesis explores two distinct lines of work leading to new practical models in response to these scenarios.First, we examine communication locality, the total number of other parties that each party communicates with in the protocol, as a new measure for an MPC protocol. Although progress has been made, the question of achieving low communication locality and round complexity at the same time for adaptive adversaries corrupting t l n/2 parties remains open. We show that by assuming a public-key infrastructure (PKI) and a symmetric-key infrastructure (SKI) the above question can be answered affirmatively, under standard assumptions. In particular, we describe a protocol with polylogarithmic communication locality and round complexity which tolerates up to t l n/2 adaptive corruptions. Our results are based on a new model of hidden random graphs obtained from the SKI, and using them to emulate a complete network in polylogarithmic rounds and polylogarithmic locality.We then examine multi-key fully homomorphic encryption (MFHE) schemes, which allow computation on data encrypted under different public keys chosen independently of each other. One of the main problems left in MFHE has been on how to deal with malicious users without trusted setup assumptions. We show how this can be done through circuit privacy, which guarantees that even if both ciphertexts and public keys are not well-formed, no information is revealed regarding the computation, other than what follows from the output on some well-formed inputs. Generalizing the result for circuit-private FHE, we provide a framework for adding circuit privacy to existing MFHE schemes.Finally, we incorporate the circuit privacy in a variant of server-assisted MPC, called on-the-fly MPC, where a server or a “cloud” performs an arbitrary dynamically chosen computation on a subset of data uploaded by multiple clients and encrypted under different keys on-the-fly. Circuit privacy allows the server to keep the algorithm used in the computation private even from a malicious adversary corrupting any number of clients. In particular, we construct a three-round on-the-fly MPC protocol with circuit privacy against malicious clients without the trusted setup.
Secure multi-party computation (MPC) is one of the most important primitives in cryptography. Several directions to construct and improve MPC protocols have been studied over the past decades. The majority of existing MPC protocols rely on assumptions such as every party communicates with every other party or every party needs to know every other party and the computation algorithm well in advance. Such assumptions can be difficult to achieve in modern large scale networks. This thesis explores two distinct lines of work leading to new practical models in response to these scenarios.First, we examine communication locality, the total number of other parties that each party communicates with in the protocol, as a new measure for an MPC protocol. Although progress has been made, the question of achieving low communication locality and round complexity at the same time for adaptive adversaries corrupting t < n/2 parties remains open. We show that by assuming a public-key infrastructure (PKI) and a symmetric-key infrastructure (SKI) the above question can be answered affirmatively, under standard assumptions. In particular, we describe a protocol with polylogarithmic communication locality and round complexity which tolerates up to t < n/2 adaptive corruptions. Our results are based on a new model of hidden random graphs obtained from the SKI, and using them to emulate a complete network in polylogarithmic rounds and polylogarithmic locality.We then examine multi-key fully homomorphic encryption (MFHE) schemes, which allow computation on data encrypted under different public keys chosen independently of each other. One of the main problems left in MFHE has been on how to deal with malicious users without trusted setup assumptions. We show how this can be done through circuit privacy, which guarantees that even if both ciphertexts and public keys are not well-formed, no information is revealed regarding the computation, other than what follows from the output on some well-formed inputs. Generalizing the result for circuit-private FHE, we provide a framework for adding circuit privacy to existing MFHE schemes.Finally, we incorporate the circuit privacy in a variant of server-assisted MPC, called on-the-fly MPC, where a server or a “cloud” performs an arbitrary dynamically chosen computation on a subset of data uploaded by multiple clients and encrypted under different keys on-the-fly. Circuit privacy allows the server to keep the algorithm used in the computation private even from a malicious adversary corrupting any number of clients. In particular, we construct a three-round on-the-fly MPC protocol with circuit privacy against malicious clients without the trusted setup.
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).
Abstract. Existing communication models for multiparty computation (MPC) either assume that all messages are delivered eventually or any message can be lost. Under the former assumption, MPC protocols guaranteeing output delivery are known. However, this assumption may not hold in some network settings like the Internet where messages can be lost due to denial of service attack or heavy network congestion. On the other hand, the latter assumption may be too conservative. Known MPC protocols developed under this assumption have an undesirable feature: output delivery is not guaranteed even only one party suffers message loss. In this work, we propose a communication model which makes an intermediate assumption on message delivery. In our model, there is a common global clock and three types of parties: (i) Corrupted parties (ii) Honest parties with connection problems (where message delivery is never guaranteed) (iii) Honest parties that can normally communicate but may lose a small fraction of messages at each round due to transient network problems. We define secure MPC under this model. Output delivery is guaranteed to type (ii) parties that do not abort and type (iii) parties. Let n be the total number of parties, ef and ec be upper bounds on the number of corrupted parties and type (ii) parties respectively. We construct a secure MPC protocol for n> 4ef + 3ec. Protocols for broadcast and verifiable secret sharing are constructed along the way. 1