In this dissertation, we study the design of secure and efficient protocols for distributed linear algebra problems. All existing solutions to the problem are either inefficient in terms of round and communication complexity and/or provide security against very weak adversaries.
We design protocols for two different adversarial settings. (i) Computational: where the adversary's computational resources are bounded, but the adversary is allowed to corrupt all but one of the participants. (ii) Information theoretic: where the adversary is unconditionally powerful, but is only allowed to corrupt a third of the participants. The security in both cases is defined in the real world/ideal world simulation paradigm, where we assume that the adversary can behave arbitrarily malicious.
Our main constructions are O(s) round protocols with O(sn2+1/s) communication for testing singularity of a shared n x n matrix, for any positive integer s, in both adversarial settings. We then use and extend these constructions to design secure protocols for computing the rank of a shared matrix and solving shared linear systems with similar efficiency. Our protocols are almost optimal in terms of round and communication complexity, as they roughly match the efficiency of the best possible protocols for the case where security is not a concern.
We use a wide range of techniques from computer algebra to reduce the problem of securely deciding singularity to the problem of secure matrix multiplication. We then design new and efficient protocols for secure matrix multiplication in both adversarial environments. In the computational setting, and when there are only two parties, we apply cut-and-choose techniques to encrypted algebraic encodings of the inputs, outputs, and intermediate values in order to prevent malicious behavior. We achieve even better amortized efficiency when running multiple instances of the protocol, via use of share-packing techniques. When the number of parties is more that two, our construction relies on efficient instantiations of the inner and outer protocols in a recently introduced compiler by Ishai et al. [35]. In the information theoretic setting, our protocol takes advantage of a homomorphic commitment scheme to achieve the improved efficiency.
In this dissertation, we study the design of secure and efficient protocols for distributed linear algebra problems. All existing solutions to the problem are either inefficient in terms of round and communication complexity and/or provide security against very weak adversaries.
We design protocols for two different adversarial settings. (i) Computational: where the adversary's computational resources are bounded, but the adversary is allowed to corrupt all but one of the participants. (ii) Information theoretic: where the adversary is unconditionally powerful, but is only allowed to corrupt a third of the participants. The security in both cases is defined in the real world/ideal world simulation paradigm, where we assume that the adversary can behave arbitrarily malicious.
Our main constructions are O(s) round protocols with O(sn2+1/s) communication for testing singularity of a shared n x n matrix, for any positive integer s, in both adversarial settings. We then use and extend these constructions to design secure protocols for computing the rank of a shared matrix and solving shared linear systems with similar efficiency. Our protocols are almost optimal in terms of round and communication complexity, as they roughly match the efficiency of the best possible protocols for the case where security is not a concern.
We use a wide range of techniques from computer algebra to reduce the problem of securely deciding singularity to the problem of secure matrix multiplication. We then design new and efficient protocols for secure matrix multiplication in both adversarial environments. In the computational setting, and when there are only two parties, we apply cut-and-choose techniques to encrypted algebraic encodings of the inputs, outputs, and intermediate values in order to prevent malicious behavior. We achieve even better amortized efficiency when running multiple instances of the protocol, via use of share-packing techniques. When the number of parties is more that two, our construction relies on efficient instantiations of the inner and outer protocols in a recently introduced compiler by Ishai et al. [35]. In the information theoretic setting, our protocol takes advantage of a homomorphic commitment scheme to achieve the improved efficiency.
Many services that people use daily require computation that depends on the private data of multiple parties. While the utility of the final result of such interactions outweighs the privacy concerns related to output release, the inputs for such computations are much more sensitive and need to be protected. Secure multiparty computation (MPC) considers the question of constructing computation protocols that reveal nothing more about their inputs than what is inherently leaked by the output. There have been strong theoretical results that demonstrate that every functionality can be computed securely. However, these protocols remain unused in practical solutions since they introduce efficiency overhead prohibitive for most applications. Generic multiparty computation techniques address homogeneous setups with respect to the resources available to the participants and the adversarial model. On the other hand, realistic scenarios present a wide diversity of heterogeneous environments where different participants have different available resources and different incentives to misbehave and collude. In this thesis we introduce techniques for multiparty computation that focus on heterogeneous settings. We present solutions tailored to address different types of asymmetric constraints and improve the efficiency of existing approaches in these scenarios. We tackle the question from three main directions: New Computational Models for MPC - We explore different computational models that enable us to overcome inherent inefficiencies of generic MPC solutions using circuit representation for the evaluated functionality. First, we show how we can use random access machines to construct MPC protocols that add only polylogarithmic overhead to the running time of the insecure version of the underlying functionality. This allows to achieve MPC constructions with computational complexity sublinear in the size for their inputs, which is very important for computations that use large databases. We also consider multivariate polynomials which yield more succinct representations for the functionalities they implement than circuits, and at the same time a large collection of problems are naturally and efficiently expressed as multivariate polynomials. We construct an MPC protocol for multivariate polynomials, which improves the communication complexity of corresponding circuit solutions, and provides currently the most efficient solution for multiparty set intersection in the fully malicious case. Outsourcing Computation - The goal in this setting is to utilize the resources of a single powerful service provider for the work that computationally weak clients need to perform on their data. We present a new paradigm for constructing verifiable computation (VC) schemes, which enables a computationally limited client to verify efficiently the result of a large computation. Our construction is based on attribute-based encryption and avoids expensive primitives such as fully homomorphic encryption andprobabilistically checkable proofs underlying existing VC schemes. Additionally our solution enjoys two new useful properties: public delegation and verification. We further introduce the model of server-aided computation where we utilize the computational power of an outsourcing party to assist the execution and improve the efficiency of MPC protocols. For this purpose we define a new adversarial model of non-collusion, which provides room for more efficient constructions that rely almost completely only on symmetric key operations, and at the same time captures realistic settings for adversarial behavior. In this model we propose protocols for generic secure computation that offload the work of most of the parties to the computation server. We also construct a specialized server-aided two party set intersection protocol that achieves better efficiencies for the two participants than existing solutions. Outsourcing in many cases concerns only data storage and while outsourcing the data of a single party is useful, providing a way for data sharing among different clients of the service is the more interesting and useful setup. However, this scenario brings new challenges for access control since the access control rules and data accesses become private data for the clients with respect to the service provide. We propose an approach that offers trade-offs between the privacy provided for the clients and the communication overhead incurred for each data access. Efficient Private Search in Practice - We consider the question of private search from a different perspective compared to traditional settings for MPC. We start with strict efficiency requirements motivated by speeds of available hardware and what is considered acceptable overhead from practical point of view. Then we adopt relaxed definitions of privacy, which still provide meaningful security guarantees while allowing us to meet the efficiency requirements. In this setting we design a security architecture and implement a system for data sharing based on encrypted search, which achieves only 30% overhead compared to non-secure solutions on realistic workloads.
Considering constant-round protocols for generating random shared values, for secure multiplication and for addition of shared values, etc are available and can be met by known techniques in all standard models of communication. Protocols are presented allowing the players to securely solve standard computational problems in linear algebra. In particular, securely, efficiently and in constant-round compute determinant of matrices product, rank of a matrix, and determine similarity between matrices. If the basic protocols (addition and multiplication, etc) are unconditionally secure, then so are our protocols. Furthermore our protocols offer more efficient solutions than previous techniques for secure linear algebra.
Abstract. We present communication efficient secure protocols for a variety of linear algebra problems. Our main building block is a protocol for computing Gaussian Elimination on encrypted data. As input for this protocol, Bob holds a k ×k matrix M, encrypted with Alice’s key. At the end of the protocol run, Bob holds an encryption of an upper-triangular matrix M ′ such that the number of nonzero elements on the diagonal equals the rank of M. The communication complexity of our protocol is roughly O(k 2). Building on Oblivious Gaussian elimination, we present secure protocols for several problems: deciding the intersection of linear and affine subspaces, picking a random vector from the intersection, and obliviously solving a set of linear equations. Our protocols match known (insecure) communication complexity lower bounds, and improve the communication complexity of both Yao’s garbled circuits and that of specific previously published protocols. 1
Abstract. We show an efficient secure two-party protocol, based on Yao’s construction, which provides security against malicious adversaries. Yao’s original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the “GMW compiler”). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs. Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running O(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao’s protocol does not yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security. Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party com-putation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a sta-tistical security parameter. These two reductions are comparable to Kilian’s reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18]. 1
We present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system. [...] Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed. We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We [...] support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure. In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.
We present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system.
Communication is often the most significant bottleneck in distributed computing. Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed.
We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We develop a clear and concise set of definitions that support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure.
In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.