Secure multiparty computation (\(\mathsf {MPC}\)) addresses the challenge of evaluating functions on secret inputs without compromising their privacy. A central question in multiparty computation is to understand the amount of communication needed to securely evaluate a circuit of size s. In this work, we revisit this fundamental question in the setting of information-theoretically secure \(\mathsf {MPC}\) in the correlated randomness model, where a trusted dealer distributes correlated random coins, independent of the inputs, to all parties before the start of the protocol. This setting is of strong theoretical interest, and has led to the most practically efficient \(\mathsf {MPC}\) protocols known to date.
Secure multiparty computation ((\mathsf {MPC})) addresses the challenge of evaluating functions on secret inputs without compromising their privacy. A central question in multiparty computation is to understand the amount of communication needed to securely evaluate a circuit of size s. In this work, we revisit this fundamental question in the setting of information-theoretically secure (\mathsf {MPC}) in the correlated randomness model, where a trusted dealer distributes correlated random coins, independent of the inputs, to all parties before the start of the protocol. This setting is of strong theoretical interest, and has led to the most practically efficient (\mathsf {MPC}) protocols known to date.
Secure multiparty computation (MPC) is a cryptographic primitive which enables multiple parties to jointly compute a function without revealing any extra information on their private inputs. Bottleneck complexity is an efficiency measure that captures the load-balancing aspect of MPC protocols, defined as the maximum amount of communication required by any party. In this work, we study the problem of establishing lower bounds on the bottleneck complexity of MPC protocols. While the previously known techniques for lower bounding total communication complexity can also be applied to bottleneck complexity, they do not provide nontrivial bounds in the correlated randomness model, which is commonly assumed by existing protocols achieving low bottleneck complexity, or they are applied only to functions of limited practical interest. We propose several novel techniques for lower bounding the bottleneck complexity of MPC protocols. Our methods derive nontrivial lower bounds even in the correlated randomness model and apply to practically relevant functions including the sum function and threshold functions. Furthermore, our lower bounds demonstrate the optimality of some existing MPC protocols in terms of bottleneck complexity or the amount of correlated randomness.
We prove two classes of lower bounds on the communication complexity of information-theoretically secure multiparty computation. The first lower bound applies to perfect passive secure multiparty computation in the standard model with n = 2t+1 parties of which t are corrupted. We show a lower bound that applies to secure evaluation of any function, assuming that each party can choose to learn or not learn the output. Specifically, we show that there is a function H^* such that for any protocol that evaluates y_i = b_i ⋅ f(x₁,...,x_n) with perfect passive security (where b_i is a private boolean input), the total communication must be at least 1/2 ∑_{i = 1}ⁿ H_f^*(x_i) bits of information. The second lower bound applies to the perfect maliciously secure setting with n = 3t+1 parties. We show that for any n and all large enough S, there exists a reactive functionality F_S taking an S-bit string as input (and with short output) such that any protocol implementing F_S with perfect malicious security must communicate Ω(nS) bits. Since the functionalities we study can be implemented with linear size circuits, the result can equivalently be stated as follows: for any n and all large enough g ∈ ℕ there exists a reactive functionality F_C doing computation specified by a Boolean circuit C with g gates, where any perfectly secure protocol implementing F_C must communicate Ω(n g) bits. The results easily extends to constructing similar functionalities defined over any fixed finite field. Using known techniques, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor lg n off for Boolean circuits). Both results also extend to the case where the threshold t is suboptimal. Namely if n = kt+s the bound is weakened by a factor O(s), which corresponds to known optimizations via packed secret-sharing.
In secure multiparty computation (MPC), mutually distrusting users collaborate to compute a function of their private data without revealing any additional information about their data to the other users. While it is known that information theoretically secure MPC is possible among n users having access to private randomness and are pairwise connected by secure, noiseless, and bidirectional links against the collusion of less than n/2 users (in the honest-but-curious model; the threshold is n/3 in the malicious model), relatively little is known about the communication and randomness complexity of secure computation, i.e., the amount of communication and randomness required to compute securely. In this paper, we employ information theoretic techniques to obtain lower bounds on communication and randomness complexity of secure MPC. We restrict ourselves to a concrete interactive setting involving three users under which all functions are securely computable against corruption of individual users in the honest-but-curious model. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to ∞). Our techniques include the use of a data processing inequality for residual information (i.e., the gap between mutual information and Gács-Körner common information), a new information inequality for three-user protocols, and the idea of distribution switching by which lower bounds computed under certain worst case scenarios can be shown to apply for the general case. Our lower bounds are shown to be tight for various functions of interest. In particular, we show concrete functions which have communication-ideal protocols, i.e., which achieve the minimum communication simultaneously on all links in the network. Also, we obtain the first explicit example of a function that incurs a higher communication cost than the input length, in the secure computation model of Feige et al. (26th Annual ACM Symposium on Theory of Computing, 1994), who had shown that such functions exist. We also show that our communication bounds imply tight lower bounds on the amount of randomness required by MPC protocols for many interesting functions.
We show that any multiparty functionality can be evaluated using a 2-round protocol with perfect correctness and perfect semihonest security, provided that the majority of parties are honest. This settles the round complexity of information-theoretic semihonest multiparty computation, resolving a longstanding open question [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294--304]. The protocol is efficient for NC1 functionalities. Furthermore, given black-box access to a one-way function, the protocol can be made efficient for any polynomial functionality, at the cost of only guaranteeing computational security. Our results are based on a new notion of multiparty randomized encoding which extends and relaxes the standard notion of randomized encoding of functions [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294--304]. The property of a multiparty randomized encoding (MPRE) is that if the functionality g is an encoding of the functionality f, then for any (permitted) coalition of players, their respective outputs and inputs in g allow them to simulate their respective inputs and outputs in f, without learning anything else, including the other outputs of f. We further introduce a new notion of effective degree, and show that the round complexity of a functionality f is characterized by the degree of its MPRE. We construct degree-2 MPREs for general functionalities in several settings under different assumptions, and use these constructions to obtain 2-round protocols. Our constructions also give rise to new protocols in the client-server model with optimal round complexity.
This thesis presents a theoretical analysis of round complexity in cryptographic sampling protocols. We study the following problem: how can n participants agree on a random sample from the distribution D without anybody knowing any secret information hidden in the chosen sample? How many rounds of interactions are needed in any such protocol? Which assumptions are required? These questions are particularly interesting in the context of multiparty computation (MPC) due to the extensive reliance (often unavoidable) on trusted setups such as common reference strings (CRSs). These are samples from known distributions made public before the beginning of the protocol. Security proofs often require CRSs to hide trapdoors. However, if these trapdoors get leaked, security is often fatally compromised. Since trusted setups are inherently single points of failure, it is desirable to generate CRSs in a distributed fashion using MPC protocols: as long as at least one of the participants remains honest, any trapdoor hidden in the CRS is guaranteed to remain secret. Previous research (Garg et al. TCC ’14) had shown that, in the setting of semi-honest security with dishonest majority, any functionality can be implemented in two rounds. In this thesis, we show that, using strong primitives such as indistinguishability obfuscation (iO), it is possible to build one-round sampling protocols. We call these constructions distributed samplers. We show that these protocols can be used to securely generate large amounts of correlated randomness with sublinear communication in a single round. We study different ways to upgrade our semi-honest construction to active security. First, we try to circumvent Cleve’s impossibility (STOC ’86) by allowing the adversary limited influence on the output of the protocol: we consider the functionality F_D^{Active} that proposes a polynomial number of different outputs to the adversary, letting it choose its favourite one (F_D^{Active} can still be used to generate CRSs). We show how to implement F_D^{Active} in one round by relying on a programmable random oracle. In subsequent work, we show that random oracles are necessary: any actively secure distributed samplers implementing F_D^{Active} needs to rely on a CRS that is non-reusable, as large as a sample from D and structured (unless D is an obliviously samplable distribution). This suggests that, without random oracles, simulation-based, actively secure distributed samplers provide no advantage over trusted dealers. We get around this impossibility by proposing new game-based definitions for actively secure distributed samplers. Hardness-preserving distributed samplers allow the removal of CRSs from MPC protocols preserving at the same time the hardness of search problems. Indistinguishability-preserving distributed samplers, on the other hand, substitute the trusted setup while preserving the functionality, however, the protocol needs to satisfy particular conditions. We show how to build distributed samplers with the defined properties by relying on extremely lossy functions, the subexponential security of iO and other primitives. Next, in the context of active security with dishonest majority, we study the feasibility of protocols producing unbiased samples with guaranteed output: to circumvent Cleve's impossibility, we assume the existence of an auxiliary functionality that, upon invocation, publishes a random , short k-bit string. We first study the question when D is the uniform distribution over {0, 1}^m where m>k. This problem is called coin tossing extension (CTE) (Bellare et al. PODC '96). We show the existence of O(1)-round CTE constructions producing an arbitrarily large quantity of unbiased randomness based on various assumptions (OWFs, DDH, QR and DCR, class groups). Our most important result is an LWE-based, one-round, UC-secure, n-party CTE protocol withstanding adaptive corruption. The protocol can be viewed as an explainable randomness extractor. By relying on distributed samplers and the auxiliary functionality, we build one-round unbiased sampling protocols for any distribution. Finally, we present a lower bound for statistically secure CTE with black-box simulation: an R-round protocol can generate at most k+R·O(log λ) bits of randomness.
Secure multi-party computation (MPC) enables multiple players to cooperatively evaluate various functions in the presence of adversaries. In this paper, we consider non-interactive MPC (NIMPC) against honest-but-curious adversaries in the information-theoretic setting, which was introduced by Beimel et al. at CRYPTO 2014. Their main focus is to realize stronger security while completely avoiding interaction, and succeeded to show that every function admits a fully robust NIMPC protocol. In this paper, we further develop the study of NIMPC. We first present a simple lower bound on the communication complexity derived from the correctness requirement of NIMPC. Secondly, we present an efficient NIMPC protocol for indicator functions, which is an important building block of NIMPC protocols. An NIMPC protocol for arbitrary functions is also constructed from the proposed NIMPC for indicator functions by using the generic compiler introduced by Beimel et al. in CRYPTO 2014. The communication complexities of NIMPC protocols presented in this paper are much more efficient than the previous ones. In fact, the gap between the lower and upper bounds of the communication complexity is reduced from exponential in the input length to quadratic . Finally, we show some improvements on the efficiency in the so-called offline-online model. Specifically, for some sets of functions, the exponential amount of offline communication reduces the online communication to almost optimum amount in the standard model.