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.
Considering secure distributed computation, also known as secure multi-party computation, from an information theoretic (i.e., Shannon) perspective is still in its infancy. To the best of the authors' knowledge there exist only some very recent results. For instance, introduce a new Shannon theoretic multiuser source model in @cite_15 and @cite_1 and characterize when a function is securely computable. In this context, they provide necessary and sufficient conditions for the existence of protocols that achieve this. Within the standard secure multi-party computation model of @cite_7 , Lee and Abbe determine in @cite_10 the least amount of randomness needed for securely computing a given function. This provides a novel notion of the complexity of a function for its secure computation. In the second part of that paper, the considerations are extended to a probabilistic source model for which the decoding error probability is required to vanish asymptotically in the block length.
@cite_10 @cite_15 @cite_1 @cite_7
1832515201 2027340571 2164014406 2092422002
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. 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. 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. How to achieve differential privacy in the distributed setting, where the dataset is distributed among the distrustful parties, is an important problem. We consider in what condition can a protocol inherit the differential privacy property of a function it computes. The heart of the problem is the secure multiparty computation of randomized function. A notion is introduced, which captures the key security problems when computing a randomized function from a deterministic one in the distributed setting. By this observation, a sufficient and necessary condition about computing a randomized function from a deterministic one is given. The above result can not only be used to determine whether a protocol computing differentially private function is secure, but also be used to construct secure one. Then we prove that the differential privacy property of a function can be inherited by the protocol computing it if the protocol privately computes it. A composition theorem of differentially private protocols is also presented. We also construct some protocols to generate random variate in the distributed setting, such as the uniform random variates and the inversion method. By using these fundamental protocols, we construct protocols of the Gaussian mechanism, the Laplace mechanism and the Exponential mechanism. Importantly, all these protocols satisfy obliviousness and so can be proved to be secure in a simulation based manner. We also provide a complexity bound of computing randomized function in the distribute setting. Finally, to show that our results are fundamental and powerful to multiparty differential privacy, we construct a differentially private empirical risk minimization protocol. Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a single, semi-honest corrupt party, since these protocols enjoy very high efficiency. We propose a new approach for secure three-party computation (3PC) that improves security while maintaining practical efficiency that is competitive with traditional information-theoretic protocols. Our protocol is based on garbled circuits and provides security against a single, malicious corrupt party. Unlike information-theoretic 3PC protocols, ours uses a constant number of rounds. Our protocol only uses inexpensive symmetric-key cryptography: hash functions, block ciphers, pseudorandom generators (in particular, no oblivious transfers) and has performance that is comparable to that of Yao's (semi-honest) 2PC protocol. We demonstrate the practicality of our protocol with an implementation based on the JustGarble framework of (S&P 2013). The implementation incorporates various optimizations including the most recent techniques for efficient circuit garbling. We perform experiments on several benchmarking circuits, in different setups. Our experiments confirm that, despite providing a more demanding security guarantee, our protocol has performance comparable to existing information-theoretic 3PC. Motivated by privacy and usability requirements in various scenarios where existing cryptographic tools (like secure multi-party computation and functional encryption) are not adequate, we introduce a new cryptographic tool called Controlled Functional Encryption (C-FE). As in functional encryption, C-FE allows a user (client) to learn only certain functions of encrypted data, using keys obtained from an authority. However, we allow (and require) the client to send a fresh key request to the authority every time it wants to evaluate a function on a ciphertext. We obtain efficient solutions by carefully combining CCA2 secure public-key encryption (or rerandomizable RCCA secure public-key encryption, depending on the nature of security desired) with Yao's garbled circuit. Our main contributions in this work include developing and for- mally defining the notion of C-FE; designing theoretical and practical constructions of C-FE schemes achieving these definitions for specific and general classes of functions; and evaluating the performance of our constructions on various application scenarios. Yao's classical millionaires' problem is about securely determining whether x > y, given two input values x, y, which are held as private inputs by two parties, respectively. The output x > y becomes known to both parties. In this paper, we consider a variant of Yao's problem in which the inputs x, y as well as the output bit x > y are encrypted. Referring to the framework of secure n-party computation based on threshold homomorphic cryptosystems as put forth by Cramer, Damgard, and Nielsen at Eurocrypt 2001, we develop solutions for integer comparison, which take as input two lists of encrypted bits representing x and y, respectively, and produce an encrypted bit indicating whether x > y as output. Secure integer comparison is an important building block for applications such as secure auctions. In this paper, our focus is on the two-party case, although most of our results extend to the multi-party case. We propose new logarithmicround and constant-round protocols for this setting, which achieve simultaneously very low communication and computational complexities. We analyze the protocols in detail and show that our solutions compare favorably to other known solutions. We present FairplayMP (for "Fairplay Multi-Party"), a system for secure multi-party computation. Secure computation is one of the great achievements of modern cryptography, enabling a set of untrusting parties to compute any function of their private inputs while revealing nothing but the result of the function. In a sense, FairplayMP lets the parties run a joint computation that emulates a trusted party which receives the inputs from the parties, computes the function, and privately informs the parties of their outputs. FairplayMP operates by receiving a high-level language description of a function and a configuration file describing the participating parties. The system compiles the function into a description as a Boolean circuit, and perform a distributed evaluation of the circuit while revealing nothing else. FairplayMP supplements the Fairplay system [16], which supported secure computation between two parties. The underlying protocol of FairplayMP is the Beaver-Micali-Rogaway (BMR) protocol which runs in a constant number of communication rounds (eight rounds in our implementation). We modified the BMR protocol in a novel way and considerably improved its performance by using the Ben-Or-Goldwasser-Wigderson (BGW) protocol for the purpose of constructing gate tables. We chose to use this protocol since we believe that the number of communication rounds is a major factor on the overall performance of the protocol. We conducted different experiments which measure the effect of different parameters on the performance of the system and demonstrate its scalability. (We can now tell, for example, that running a second-price auction between four bidders, using five computation players, takes about 8 seconds.) Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting where the inputs are held by different parties and may be extremely large. Furthermore, for some applications, the parties want to compute a function of their inputs securely without revealing more information than necessary. In this work, we study the question of simultaneously addressing the above efficiency and security concerns via what we call secure approximations.We start by extending standard definitions of secure (exact) computation to the setting of secure approximations. Our definitions guarantee that no additional information is revealed by the approximation beyond what follows from the output of the function being approximated. We then study the complexity of specific secure approximation problems. In particular, we obtain a sublinear-communication protocol for securely approximating the Hamming distance and a polynomial-time protocol for securely approximating the permanent and related #P-hard problems. Consider the following scenario: Alice and Bob, two parties who share no secret key initially but whose goal it is to generate a (large amount of) information-theoretically secure (or unconditionally secure) shared secret key, are connected only by an insecure public channel to which an eavesdropper Eve has perfect (read) access. Moreover, there exists a satelite broadcasting random bits at a very low signal power. Alice and Bob can receive these bits with certain bit error probabilities ?A and ?B, respectively (e.g. ?A = ?B = 30 ) while Eve is assumed to receive the same bits much more reliably with bit error probability ?E ? ?A, ?B (e.g. ?E = 1 ). The errors on the three channels are assumed to occur at least partially independently. Practical protocols are discussed by which Alice and Bob can generate a secret key despite the facts that Eve possesses more information than both of them and is assumed to have unlimited computational resources as well as complete knowledge of the protocols.The described scenario is a special case of a much more general setup in which Alice, Bob and Eve are assumed to know random variables X, Y and Z jointly distributed according to some probability distribution PXYZ, respectively. The results of this paper suggest to build cryptographic systems that are provably secure against enemies with unlimited computing power under realistic assumptions about the partial independence of the noise on the involved communication channels. A fundamental task in modern cryptography is the joint computation of a function which has two inputs, one from Alice and one from Bob, such that neither of the two can learn more about the other's input than what is implied by the value of the function. In this Letter, we show that any quantum protocol for the computation of a classical deterministic function that outputs the result to both parties (two-sided computation) and that is secure against a cheating Bob can be completely broken by a cheating Alice. Whereas it is known that quantum protocols for this task cannot be completely secure, our result implies that security for one party implies complete insecurity for the other. Our findings stand in stark contrast to recent protocols for weak coin tossing and highlight the limits of cryptography within quantum mechanics. We remark that our conclusions remain valid, even if security is only required to be approximate and if the function that is computed for Bob is different from that of Alice. A completely insecure communication channel can only be transformed into an unconditionally secure channel if some information-theoretic primitive is given to start from. All previous approaches to realizing such authenticity and privacy from weak primitives were symmetric in the sense that security for both parties was achieved. We show that asymmetric information-theoretic security can, however, be obtained at a substantially lower price than two-way security|like in the computational-security setting, as the example of public-key cryptography demonstrates. In addition to this, we show that also an unconditionally secure bidirectional channel can be obtained under weaker conditions than previously known. One consequence of these results is that the assumption usually made in the context of quantum key distribution that the two parties share a short key initially is unnecessarily strong. Secure two-party computation enables two parties to evaluate a function cooperatively without revealing to either party anything beyond the function’s output. The garbled-circuit technique, a generic approach to secure two-party computation for semi-honest participants, was developed by Yao in the 1980s, but has been viewed as being of limited practical significance due to its inefficiency. We demonstrate several techniques for improving the running time and memory requirements of the garbled-circuit technique, resulting in an implementation of generic secure two-party computation that is significantly faster than any previously reported while also scaling to arbitrarily large circuits. We validate our approach by demonstrating secure computation of circuits with over 10 9 gates at a rate of roughly 10 ms per garbled gate, and showing order-of-magnitude improvements over the best previous privacy-preserving protocols for computing Hamming distance, Levenshtein distance, Smith-Waterman genome alignment, and AES. Distributed learning allows a group of independent data owners to collaboratively learn a model over their data sets without exposing their private data. We present a distributed learning approach that combines differential privacy with secure multi-party computation. We explore two popular methods of differential privacy, output perturbation and gradient perturbation, and advance the state-of-the-art for both methods in the distributed learning setting. In our output perturbation method, the parties combine local models within a secure computation and then add the required differential privacy noise before revealing the model. In our gradient perturbation method, the data owners collaboratively train a global model via an iterative learning algorithm. At each iteration, the parties aggregate their local gradients within a secure computation, adding sufficient noise to ensure privacy before the gradient updates are revealed. For both methods, we show that the noise can be reduced in the multi-party setting by adding the noise inside the secure computation after aggregation, asymptotically improving upon the best previous results. Experiments on real world data sets demonstrate that our methods provide substantial utility gains for typical privacy requirements. A secure function evaluation protocol allows two parties to jointly compute a function f(x,y) of their inputs in a manner not leaking more information than necessary. A major result in this field is: “any function f that can be computed using polynomial resources can be computed securely using polynomial resources” (where “resources” refers to communication and computation). This result follows by a general transformation from any circuit for f to a secure protocol that evaluates f . Although the resources used by protocols resulting from this transformation are polynomial in the circuit size, they are much higher (in general) than those required for an insecure computation of f . We propose a new methodology for designing secure protocols, utilizing the communication complexity tree (or branching program) representation of f . We start with an efficient (insecure) protocol for f and transform it into a secure protocol. In other words, any function f that can be computed using communication complexity c can be can be computed securely using communication complexity that is polynomial in c and a security parameter''. We show several simple applications of this new methodology resulting in protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the Millionaires problem, where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation. Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything but the result. Over recent years, secure computation has become practical and considerable effort has been made to make it more and more efficient. A highly important tool in the design of two-party protocols is Yao's garbled circuit construction (Yao 1986), and multiple optimizations on this primitive have led to performance improvements of orders of magnitude over the last years. However, many of these improvements come at the price of making very strong assumptions on the underlying cryptographic primitives being used (e.g., that AES is secure for related keys, that it is circular secure, and even that it behaves like a random permutation when keyed with a public fixed key). The justification behind making these strong assumptions has been that otherwise it is not possible to achieve fast garbling and thus fast secure computation. In this paper, we take a step back and examine whether it is really the case that such strong assumptions are needed. We provide new methods for garbling that are secure solely under the assumption that the primitive used (e.g., AES) is a pseudorandom function. Our results show that in many cases, the penalty incurred is not significant, and so a more conservative approach to the assumptions being used can be adopted. Consider a multi-layered graph, where the different layers correspond to different proprietary social networks on the same ground set of users. Suppose that the owners of the different networks (called hosts) are mutually non-trusting parties: how can they compute a centrality score for each of the users using all the layers, but without disclosing information about their private graphs? Under this setting we study a suite of three centrality measures whose algebraic structure allows performing that computation with provable security and efficiency. The first measure counts the nodes reachable from a node within a given radius. The second measure extends the first one by counting the number of paths between any two nodes. The final one is a generalization to the multi-layered graph case: not only the number of paths is counted, but also the multiplicity of these paths in the different layers is considered. We devise a suite of multiparty protocols to compute those centrality measures, which are all provably secure in the information-theoretic sense. One typical challenge and limitation of secure multiparty computation protocols is their scalability. We tackle this problem and devise a protocol which is highly scalable and still provably secure. We test our protocols on several real-world multi-layered graphs: interestingly, the protocol to compute the most sensitive measure (i.e., the multi-layered centrality) is also the most scalable one and can be efficiently run on very large networks. We construct functional encryption schemes for polynomial-time computable functions secure against an a-priori bounded polynomial number of collusions. Our constructions require only semantically secure public-key encryption schemes and pseudorandom generators computable by small-depth circuits known to be implied by most concrete intractability assumptions. For certain special cases such as predicate encryption schemes with public index, the construction requires only semantically secure encryption schemes. Along the way, we show a "bootstrapping theorem" that builds a q-query functional encryption scheme for arbitrary functions starting from a q-query functional encryption scheme for bounded-degree functions. All our constructions rely heavily on techniques from secure multi-party computation and randomized encodings. Our constructions are secure under a strong simulation-based definition of functional encryption. We consider the problem of computing the intersection of private datasets of two parties, where the datasets contain lists of elements taken from a large domain. This problem has many applications for online collaboration. We present protocols, based on the use of homomorphic encryption and balanced hashing, for both semi-honest and malicious environments. For lists of length k, we obtain O(k) communication overhead and O(k ln ln k) computation. The protocol for the semi-honest environment is secure in the standard model, while the protocol for the malicious environment is secure in the random oracle model. We also consider the problem of approximating the size of the intersection, show a linear lower-bound for the communication overhead of solving this problem, and provide a suitable secure protocol. Lastly, we investigate other variants of the matching problem, including extending the protocol to the multi-party setting as well as considering the problem of approximate matching. All information-theoretically secure key agreement protocols (e.g. based on quantum cryptography or on noisy channels) described in the literature are secure only against passive adversaries in the sense that they assume the existence of an authenticated public channel. The goal of this paper is to investigate information-theoretic security even against active adversaries with complete control over the communication channel connecting the two parties who want to agree on a secret key. Several impossibility results are proved and some scenarios are characterized in which secret-key agreement secure against active adversaries is possible. In particular, when each of the parties, including the adversary, can observe a sequence of random variables that are correlated between the parties, the rate at which key agreement against active adversaries is possible is characterized completely: it is either 0 or equal to the rate achievable against passive adversaries, and the condition for distinguishing between the two cases is given.