Research On Several Secure Multi-Party Computation Problems And Applications

With the fast development of network and distributed computing, the com-putation mode of multi-party collaborative computation has attracted more and more interest. But, we have to concern about the data-privacy problem dur-ing the cooperation computation. And secure multi-party computation (SMC) is presented to solve this data-privacy problem. The main research of SMC is how to jointly complete a task when keeping each party’s input privacy, without leaking any information of each party.SMC problem was first proposed by A.C. Yao in1980s, and attracted more and more attention of researchist. Now, it is a new and important area in cryp-tography. The one hand, it can provide theoretical foundation of application-oriented security protocol and security architecture. SMC is abstracted from the practical problems which need privacy requirements, and research of these problems, as well as some of the conclusions have guiding significance for spe-cific cryptography problems. On the other hand, SMC has a strong application background. SMC has been applied to many computing problems, such as data mining, data query, scientific computing, geometry or set relation determina-tion, statistical analysis, and so on. Therefore, the research of SMC is valuable in theory and practice.There are already many results of SMC research, but there are still a lot of open problems which are worthy of investigation in multi-party computation related areas. Some more practical theoretical models need to be investigated in the study of basic theory and more efficient underlying protocols used as basic building blocks need to be designed. Besides, more practical and simpler SMC protocols are designed to meet more and more practical application. This disser-tation mainly focus on three SMC problems which are privacy-preserving da-ta comparison problem, privacy-preserving geometry computation and privacy-preserving query problem. And the main research contents are as follows:1. Privacy-preserving data comparison problem is researched.privacy-preserving data comparison protocols are abstract of application problems, as well as basic tools for solving SMC problems. A privacy-preserving vector e- quivalency determination problem which is an extension of the socialist million-aire problem is presented, and four solutions are also given. The main content is as follows:First, executing the socialist millionaire protocol to determine the equivalency of each component of the vector, and the equivalency of the two vectors are determined; Then, with the aid of scalar product protocol, an efficient privacy-preserving vector equivalency determination protocol is pro-posed and the correctness and security are also analyzed. And two privacy-preserving vector equivalency determination protocols are presented in the real domain with the correctness and security analyzed. At the end, an efficien-t privacy-preserving data comparison protocol in real domain is presented and the analysis is given.2. Privacy-preserving geometry computation problem is researched. Three current research framework and four kinds of sub-problems which are privacy-preserving graph-inclusion problem, privacy-preserving intersection problem, privacy-preserving set-distance problem and privacy-preserving convex hul-1problem are summed up. The description of possible scenarios for these protocols are also given. Considering a new parameter about time, based on the privacy-preserving vector equivalency determination protocol, a privacy-preserving dynamic point-point distance determination protocol based on semi-honest is proposed, and an n-dimension privacy-preserving dynamic point-point on two lines distance determination protocol is proposed, which is extended to a class of dynamic point in n-dimension. The correctness and security are also analyzed.3. Privacy-preserving query problem is researched. With the aid of dis-tributed El Gamal encryption and mix network, a privacy-preserving query pro-tocol is presented to solve the privacy-preserving query problem. And the cor-rectness and security are also given out. Then an improved privacy-preserving query protocol is proposed to solve the situation where the server may complete too much computation in a distributed system.