The problem of three-party secure computation, where a function of private data of two parties is to be computed by a third party without revealing information beyond respective inputs or outputs is considered. New and better lower bounds on the amount of communication required between the parties to guarantee zero probability of error in the computation and achieve information-theoretic security are derived. Protocols are presented and proved to be optimal in some cases by showing that they achieve the improved lower bounds.
The problem of three-party secure computation, where a function of private data of two parties is to be computed by a third party without revealing information beyond respective inputs or outputs is considered. New and better lower bounds on the amount of communication required between the parties to guarantee zero probability of error in the computation and achieve information-theoretic security are derived. Protocols are presented and proved to be optimal in some cases by showing that they achieve the improved lower bounds.
In information theoretically secure multiparty computation, several mutually distrusting users want to jointly compute a function of their private data such that users do not learn any additional information about other users' data other than what they can infer from their own data and the function value they compute. In this work we consider asymptotically secure computation - where vanishing probability of error and vanishing information leakage are allowed as block lengths become large - in a three user setting, where two users have inputs and third user securely computes the output of a function on these two inputs. We provide generic lower bounds on the amount of communication required among users and the total amount of private randomness needed to compute any function in this three-user model. We also consider some examples where our bounds are tight. Our lower bounds are derived for the honest-but-curious security model and hence also apply for the malicious model.
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.
The question of whether and how mutually distrusting parties can collaborate is a central theme in cryptography. The goal of secure function computation is to ensure that parties may correctly compute functions of their data without learning additional information. A remarkable result of Ben Or, Goldwasser, and Wigderson from 1988 shows that it is possible for parties connected by pairwise, private, noise-free links to compute functions with zero error and perfect information theoretic security provided the number of parties who may collude meets a certain threshold; specifically, if the colluders form a strict minority for the honest-but-curious model and they are strictly less than a third for the malicious model. In this paper we provide basic lowerbounds on the amount of communication required to compute with zero-error and perfect security in a three-party setting under the honest-but-curious model.
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.
Non-interactive secure multiparty computation is a method to share and compute a private functionfamongnparties holding private inputs xi with 1nin the information theoretical setting. Each party locally computes a message from a share offand send it to a referee in parallel. The referee obtains the output f (xi,… , xn) while keepingfand xi private other than what can be inferred from the output. The communication complexity is evaluated by the maximum length of shares and messages. In the previous work, several kinds of function families, upper and lower bounds have been improved and the only gaps remaining are for the group products and the Abelian programs (including symmetric functions). This paper improves the communication complexity of both function families towards the optimum by deriving a new lower bound for the group products that matches the previous upper bound (up to a constant factor) and the first asymptotically optimal upper bound for the Abelian programs.
The goal of secure two-party computation is to enable two parties to cooperatively evaluate a function that takes private data from both parties as input without exposing any of the private data. At the end of the computation, the participants learn nothing more than the output of the function. The two-party secure computation systems have three properties: (1) the application involves inputs from two independent parties; (2) each party wants to keep its own data secret; and (3) the participants agree to reveal the output of the computation. That is, the result itself does not imply too much information about either party's private input. Informally, the security requirements are that nothing is learned from the protocol other than the output (privacy), and that the output is distributed according to the prescribed functionality (correctness). The threat models in the two-party computation assume the presence of three different types of adversaries: 1) Semi honest, 2) Malicious and 3) Covert.