In this thesis, we study two fundamental areas of secure computation over a network.First, we study general two-party secure computation, where two mutually distrustful parties are trying to compute an arbitrary function of their inputs, without revealing any extra information (even if one of them is malicious).We prove that, if any nontrivial function can be so computed, then so can every other function.That is, every non-trivial function is complete for two-party secure computation.Consequently, the complexity assumptions sufficient and/or necessary for securely computing f are the same for every non-trivial function f.Next, we study the concrete problem of secure database access, where the privacy of both the database and the user is to be protected from each other and from all other participating or eavesdropping parties.We are interested in practical and theoretical aspects of this problem, addressing issues of efficiency, security, and complexity.More specifically, we start from the model of private information retrieval (PIR), where users are trying to retrieve information from a database while keeping their queries private from the database owner.We then explore the following directions: * We study the necessary assumptions for single server PIR with low communication.We prove that oblivious transfer is necessary, implying that PIR is a complete primitive for secure computation, and that computational SPIR protocols (defined below) can be efficiently constructed from PIR protocols.* We introduce the model of SPIR, where the privacy of the data, as well as the user, is guaranteed.We show how to efficiently transform PIR protocols into SPIR protocols, for both the information-theoretic and computational settings. "We introduce the random server model for PIR, and show how to use it to achieve information theoretic solutions in which the database need not give away its data to be replicated, and with minimal on-line computation for the database.
In this thesis, we study two fundamental areas of secure computation over a network.First, we study general two-party secure computation, where two mutually distrustful parties are trying to compute an arbitrary function of their inputs, without revealing any extra information (even if one of them is malicious).We prove that, if any nontrivial function can be so computed, then so can every other function.That is, every non-trivial function is complete for two-party secure computation.Consequently, the complexity assumptions sufficient and/or necessary for securely computing f are the same for every non-trivial function f.Next, we study the concrete problem of secure database access, where the privacy of both the database and the user is to be protected from each other and from all other participating or eavesdropping parties.We are interested in practical and theoretical aspects of this problem, addressing issues of efficiency, security, and complexity.More specifically, we start from the model of private information retrieval (PIR), where users are trying to retrieve information from a database while keeping their queries private from the database owner.We then explore the following directions: * We study the necessary assumptions for single server PIR with low communication.We prove that oblivious transfer is necessary, implying that PIR is a complete primitive for secure computation, and that computational SPIR protocols (defined below) can be efficiently constructed from PIR protocols.* We introduce the model of SPIR, where the privacy of the data, as well as the user, is guaranteed.We show how to efficiently transform PIR protocols into SPIR protocols, for both the information-theoretic and computational settings. "We introduce the random server model for PIR, and show how to use it to achieve information theoretic solutions in which the database need not give away its data to be replicated, and with minimal on-line computation for the database.
Security and privacy are of paramount importance in the modern information age. Secure multi-party computation and private information retrieval are canonical and representative problems in cryptography that capture the key challenges in understanding the fundamentals of security and privacy. In this dissertation, we use information theoretic tools to tackle these two classical cryptographic primitives. In the first part, we consider the secure multi-party computation problem, where multiple users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We present an efficient protocol in terms of randomness cost to securely compute a vector linear function. In the second part, we discuss the symmetric private information retrieval problem, where a user wishes to retrieve one message from a number of replicated databases while keeping the desired message index a secret from each individual database. Further, the user learns nothing about the other messages. We present an optimal protocol that achieves the minimum upload cost for symmetric private information retrieval, i.e., the queries sent from the user to the databases have the minimum number of bits.
In the problem of Secure Multi-party Computation, the objective is to design a protocol that allows a group of parties to securely compute functions of their collective private data, while ensuring that no party reveals any more information about its private data other than what must be inherently revealed by the computation results (privacy) and that no parties can disrupt or influence the computation results beyond the effects of changing their input data (correctness and consistency). Information theoretic approaches toward this problem, that provide provable (unconditional) security guarantees even against adversarial parties that have unbounded computational power, have established that general computation is possible in a variety of scenarios. However, these general solutions are not always efficient or finely tuned to the requirements of specific problems and applications.
The focus of this thesis is on the development of information theoretic approaches for multi-party computation applications with the common theme of secure and efficient computation and inference over a distributed data network. Specific applications include: 1) private information retrieval, where the objective is to privately retrieve data without revealing what was selected; 2) secure statistical analysis, the problem of extracting statistics without revealing anything else about the underlying data; 3) secure sampling, which is the secure generation of new data with a given distribution; and 4) secure authentication, where the identity of a party needs to authenticated via inference on his/her credentials and stored registration data.
The contributions of this thesis toward addressing these applications include the following: The development of an Oblivious Transfer (OT) protocol, applicable to private information retrieval, that trades off a small amount of privacy while being several times more efficient than other OT protocols. The efficiency of general se- cure two-party computation via OT realized from noisy channels is also analyzed. A technique for approximate secure multi-party computation applicable to secure statistical analysis of large scale distributed databases is developed. By exploiting a dimensionality reduction and the structure of a broad class of functions based on the computed statistics, the feasibility of simultaneously achieving both arbitrarily high accuracy and arbitrarily high communication efficiency is demonstrated. The region of distributions that can be securely sampled in the two-party scenario is characterized. It is further established that for those distributions, it can be accomplished with a protocol that only sends one message. Inner and outer bounds on the region of distributions that can be securely sampled in the general multi-party scenario are also developed. A new three-party protocol, applicable to the problem of secure biometric authentication, that securely computes the Hamming distance even when one of the parties arbitrarily deviates from the protocol is proposed and analyzed. A two-factor secure biometric authentication system that is robust against the compromise of registered biometric data, allowing for revocability and resistance against cross-enrollment attacks is also proposed.
In this dissertation, we address several issues that arise in protecting communication between parties, as well as in the area of secure function evaluation. Intuitively, the notion of secure function evaluation is clear and natural: several parties wish to compute some function of their inputs without revealing any information about the inputs, other than what is implied by the value of the function. Research included in this dissertation follows three main directions, briefly described below. The first direction (Chapters 3 and 4) is the design of efficient protocols for concrete functions of interest. Specifically, we present new, more efficient protocols for securely computing the Greater Than (GT) function on the inputs of two parties. Secure evaluation of GT is frequently needed in financial transactions. We introduce new primitives, which are convenient building blocks for more complex tasks, and generalize our GT solutions to satisfy them. Based on this, we construct secure auction protocols, protocols for determining whether an integer lies on an interval, and others. The second direction (Chapter 5) is a fundamental approach to secure evaluation of any function, given as a boolean circuit. We present a very efficient information-theoretic (IT) reduction from the problem of secure evaluation of a polysize formula (or, equivalently, a log-depth boolean circuit) to Oblivious Transfer (a fundamental well-researched cryptographic primitive). Our cost of evaluating each gate of the formula is quadratic in its depth, while in previous reductions it was exponential. Our constructions imply efficient one-round protocols for evaluation of polysize formulas on the players' inputs. We extend our solutions to evaluation of polysize circuits, at the cost of having only computational security. The third direction (Chapter 6) is research on key exchange (KE). In contrast with the previous two directions, here the goal is for two parties to protect their communication against eavesdropping and active interference of an external attacker. KE is a basic procedure, frequently used to establish secure channels between parties. It is a prerequisite to a large number of protocols, including those of the above two directions. We demonstrate a subtle flaw in a previous family of KE protocols and give new KE definitions for the following practical "bank" setting. Here, a server wishes to exchange a key with a client. They have a shared password, and the client carries a "bank card", capable of storing several cryptographic keys. Finally, we present new, more efficient KE protocols for this setting, and prove their security.
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.
Private information retrieval (PIR) is an important protocol in cryptographic community to ensure privacy of the user when retrieving information from untrusted databases. In a variation to this problem, symmetric private information retrieval (SPIR) is a protocol which ensures the privacy of user as well as databases. A major drawback for the majority of existing works on information theoretic PIR and SPIR is that they focus on scenarios where all databases store the entire data set (i.e. replicated databases). The goal of this thesis is to present PIR and SPIR schemes for storage constrained databases. For both PIR and SPIR, we present a systematic approach to utilize storage constrained databases. The technical contribution involves two main parts: (a) a careful storage scheme to split and store messages across databases; and (b) construction of information theoretic PIR and SPIR schemes from such databases. We also compare our results to the fully replicated scenario, as well as compare the differences between the communication overhead of PIR and SPIR schemes.
In the setting of secure multiparty computation, several distrustful parties wish to carry out a distributed computing task on their local private data while satisfying several security properties such as correctness, privacy, independence of inputs and fairness. The aim of secure multiparty computation (MPC) is to enable the parties to carry out the computation in a secure manner, eliminating any attempt of an adversarial entity to harm the execution. The concept of secure computation is very general and fundamental in cryptography, and models any distributed computing task, including simple computations as coin-tossing and broadcast, as well as more complex tasks such as electronic auctions and anonymous transactions. In this thesis, we study two foundational aspects of secure computation: perfect security and fairness. In the first part of this thesis, we study perfect security in secure computation. A protocol that is perfectly secure cannot be broken even when the adversary has unlimited computational power and its security holds unconditionally. One of the most fundamental results of secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. When the adversary is semi-honest this holds as long as t < n/2 parties are corrupted, and when the adversary is malicious this holds as long as t < n/3 parties are corrupted. Unfortunately, a full proof of these results was never published. In this thesis, we remedy this situation and provide a full proof of security of the BGW protocol. This also includes a full description of the protocol for the malicious setting. In addition to the above, we observe that by some simple and natural modifications, the BGW protocol can be significantly simplified and one of its expensive (and perhaps most complicated) subprotocols can be saved. We present a new multiplication protocol that is based on the original construction, but is simpler and achieves higher efficiency. In the second part of this thesis, we study fairness in secure two party computation. Informally, the fairness property guarantees that if one party receives its output, then the other party does too. The well-known impossibility result of Cleve (STOC 1986) implies that, in general, it is impossible to securely compute a function with complete fairness without an honest majority. Until recently, the accepted belief has been that nothing non-trivial can be computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist some non-trivial (deterministic, finite-domain) Boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. We focus on this question and give both positive and negative results. We first characterize