text: In this paper, the problem of securely computing a function over the binary modulo-2 adder multiple-access wiretap channel is considered. The problem involves a legitimate receiver that wishes to reliably and efficiently compute a function of distributed binary sources while an eavesdropper has to be kept ignorant of them. In order to characterize the corresponding fundamental limit, the notion of secrecy computation-capacity is introduced. Although determining the secrecy computation-capacity is challenging for arbitrary functions, it surprisingly turns out that if the function perfectly matches the algebraic structure of the channel and the joint source distribution fulfills certain conditions, the secrecy computation-capacity equals the computation capacity, which is the supremum of all achievable computation rates without secrecy constraints. Unlike the case of securely transmitting messages, no additional randomness is needed at the encoders nor does the legitimate receiver need any advantage over the eavesdropper. The results therefore show that the problem of securely computing a function over a multiple-access wiretap channel may significantly differ from the one of securely communicating messages.
  @cite_3: 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.
  @cite_10: In secure multi-party computations (SMC), parties wish to compute a function on their private data without revealing more information about their data than what the function reveals. In this paper, we investigate two Shannontype questions on this problem. We first consider the traditional one-shot model for SMC which does not assume a probabilistic prior on the data. In this model, private communication and randomness are the key enablers to secure computing, and we investigate a notion of randomness cost and capacity. We then move to a probabilistic model for the data, and propose a Shannon model for discrete memoryless SMC. In this model, correlations among data are the key enablers for secure computing, and we investigate a notion of dependency which permits the secure computation of a function. While the models and questions are general, this paper focuses on summation functions and relies on polar code constructions.
  @cite_12: In secure multiparty computation, mutually distrusting users in a network want to collaborate to compute functions of data which is distributed among the users. The users should not learn any additional information about the data of others than what they may infer from their own data and the functions they are computing. Previous works have mostly considered the worst case context (i.e., without assuming any distribution for the data); Lee and Abbe (2014) is a notable exception. Here, we study the average case (i.e., we work with a distribution on the data) where correctness and privacy is only desired asymptotically. For concreteness and simplicity, we consider a secure version of the function computation problem of K "orner and Marton (1979) where two users observe a doubly symmetric binary source with parameter p and the third user wants to compute the XOR. We show that the amount of communication and randomness resources required depends on the level of correctness desired. When zero-error and perfect privacy are required, the results of (2014) show that it can be achieved if and only if a total rate of 1 bit is communicated between every pair of users and private randomness at the rate of 1 is used up. In contrast, we show here that, if we only want the probability of error to vanish asymptotically in block length, it can be achieved by a lower rate (binary entropy of p) for all the links and for private randomness; this also guarantees perfect privacy. We also show that no smaller rates are possible even if privacy is only required asymptotically.
summary: In @cite_12 , take a distributed source coding approach to the problem of securely computing the modulo-2 sum of two distributed binary sources. Similarly to @cite_10 , they assume the data to be drawn from some joint memoryless source and derive bounds on the amount of randomness and communication needed to asymptotically achieve secrecy. In @cite_3 , the results are extended to arbitrary functions.