A study of several specific secure two -party computation problems

Alice has a private input x (of any data type, such as a number, a matrix or a data set). Bob has another private input y. Alice and Bob want to cooperatively conduct a specific computation on x and y without disclosing to the other person any information about her or his private input except for what could be derived from the results. This problem is a Secure Two-party Computation (STC) problem, which has been extensively studied in the past. Several generic solutions have been proposed to solve the general STC problem; however the generic solutions are often too inefficient to be practical. Therefore, in this dissertation, we study several specific STC problems with the goal of finding more efficient solutions than the generic ones. We introduce a number of specific STC problems in the domains of scientific computation, statistical analysis, computational geometry and database query. Most of the problems have not been studied before in the literature. To solve these problems: (1) We investigate how data perturbation could be used to hide data. Data perturbation hides a datum by adding to it a random number. We show that this technique is effective in preserving privacy. (2) We explore how domain specific knowledge can improve the efficiency of the solutions that we develop over the generic solutions that do not consider domain specific knowledge. We show that such knowledge is important in both hiding data and achieving higher efficiency. (3) We also introduce a number of common building blocks that are useful in solving secure two-party computation problems in various computation domains