Rapid advances in computer technologies and their growing acceptance by society, industry, business and governments have stimulated dramatic change of the information technology landscape. This change is not without tensions. The one most prominent is between the global accessibility of information and information protection. Information collected by various institutions and businesses is normally stored in large globally accessible databases. Global accessibility allows business and industry to expand their markets. Unfortunately the price to pay is a continual deterioration of information security and privacy of their clients.
In recent years, database privacy has received considerable attention from the research community. The main focus of this research has been on the balance between efficiency of information management (such as storing, sharing, updating) and privacy issues (preserving secrecy of personal data while allowing release of some related information). There are many works that have identified a collection of database operations together with appropriate cryptographic protocols, which preserve privacy of underlying personal data items. Unfortunately, a majority of the privacy-preserving operations require either a relaxation of underlying security requirements or impose severe limitations on efficiency.
In this thesis, we examine several specific problems that fall under the heading of privacy-preserving dataset operations. We design efficient protocols for these problems, and analyze their security and correctness in the presence of attackers.
We first propose two protocols for the secure disjointness test between two private datasets. Previous works for this problem either have a high round complexity, require a large computation overhead, or assume weaker security requirements. In order to design efficient protocols for these problems, we employ a novel combination of techniques that applies Sylvester matrices, secret sharing and the well-known secure determinant evaluation. By using secret sharing techniques to construct Sylvester matrix based on two datasets and to compute its determinant, we are able to increase the efficiency of our privacy-preserving set disjointness tests without compromising their security. In addition, our protocols are unconditionally secure against both honest-but-curious and malicious adversaries.
At Eurocrypt’04, Freedman, Nissim and Pinkas introduced a fuzzy private matching problem. The problem is defined as follows. Given two parties, each of them having a set of vectors where each vector has $T$ integer components, the fuzzy private matching is to secure test if each
vector of one set matches any vector of another set for at least $t$ components where $t < T$. In the conclusion of their paper, they asked whether it was possible to design a fuzzy private matching
protocol without incurring a communication complexity with the factor $T\choose t$ and with a malicious model. We answer their question in the affirmative and present two efficient protocols. They are based on Reed-Solomon codes with polynomial encoding and reconstruction algorithms. We also employ homomorphic encryption to ensure the privacy of the datasets. Comparing with the previous protocols, our protocols are more efficient in terms of their communication and computation overhead. Moreover, our protocols are provably secure against malicious adversaries.
We next investigate various privacy-preserving set operations that are performed by parties that are connected via an insecure communication network. The motivation behind this line of research is a growing demand for database outsourcing, where a client’s database is stored at an external service provider. However, the privacy of the outsourced database is at risk. To protect its privacy, the client could encrypt all the data stored in the provider’s server with his public-key. In general, however, querying on such encrypted database could be extremely expensive; and in some cases this may not even be possible without letting a third party know the secret-key. By combining secret sharing scheme and homomorphic encryption, we propose five protocols for performing various privacy-preserving set operations efficiently in the case of the dataset being outsourced.
We also consider the following problem. Given two parties, each of them holding a set of integer components, assume that both sets are of the same size. The parties would like to interact with each other by running a protocol so, after its execution, they know whether all components of one set are greater than the corresponding components of another without revealing any information about the integer components of their respective sets. This is so-called secure vector
dominance problem in the literature. We proposed four protocols that offer a solution to the above problem. Our protocols apply homomorphic encryption together with the bitwise XOR technique that allows the two parties to test vector dominance in an efficient and secure way. Comparing to the existing protocols, our solution provides better round, communication and computation complexities.