Research On Some Basic Protocols And Applications Of Secure Multi-party Computation

Secure Multi-party Computation (SMC) is a computation among a set of participants who do not have confidence in one another, in which participants collaborate on desired tasks but do not reveal private information of their own. Since it was initially suggested by A.C.Yao in the 1980s, SMC have been a major part of modern cryptography and attracted numerous researchers' interest. Subsequently, many significant results were presented. Existing researches on SMC may be classified into two categories. One is the general study of SMC, including study of definition of security, secure models, adversary models, general theorems of SMC, and general techniques for designing any SMC protocols. Many results that refer to general study of SMC have been presented, for example, adequate definitions of security in semi-honest model and in malicious model have been developed, some feasibility results have been described, and paradigms used in the construction of SMC protocols for computing any desired functionality have been developed. On the other hand, when cooperative computing and privacy become more and more important, SMC is introduced into various applications, including data mining, computation geometry, statistical analysis, scientific computing, electronic voting, etc, and SMC is employed to protect privacy in practical applications. Although general solutions to any SMC problems is useful, most researchers realize that using the general solution for special cases of multi-party computation can be impractical, special solutions should be developed for special cases for efficiency reasons. As a result, many secure protocols for solving specific problems are designed out, for example, several protocols for privacy-preserving data mining, for privacy-preserving computation geometry, for secure statistical analysis, etc.Although many papers on SMC have been presented, it is necessary to refine existing results of SMC and design new protocols for new problems. For theoretical study, more practical security model needs to definite. For the design of secure protocol, existing basic protocols for computing basic functionalities are not adequate, and new basic functionalities from applications need new SMC basic protocols. For solving practical application problems, existing protocols are not adequate yet. Not only the design of new SMC protocols for new problems but also the improvement in existing solutions to SMC problems needs further work.With this concern, the main research content of this dissertation is as follows,1) Research on applicability of security models and security analysis, discussing the suitable and efficient methods of security analysis.2) Research on basic problems of SMC, designing several basic protocols that can be considered as new tools for the design of SMC protocols for solving application problems.3) Studying problems of privacy-preserving association rules mining, designing SMC protocols for protecting private information in various association rules mining over horizontal partitioned data set.4) Studying the applications of SMC in computation geometry, constructing new protocols for preserving privacy in several problems of computation geometry.5) Studying application of SMC in secure query, constructing practical schemes for secure query.Correspondingly, the main contributions of this dissertation are as follows,1) We discuss the feasibility of constructing new models of security analysis, and analyze the relation among various security models. We claim that it is reasonable to choose suitable security model depending on requirement of the design of protocols and this claim is considered as basic idea for security analysis in this dissertation.2) We present several new basic secure protocols for computing basic functionalities, including a new protocol for secure set union that is more efficient than existing protocol, a secure two-party protocol for multiplication of two sharing secrets, and a secure two-party protocol for multiplying two polynomials. Above basic protocols can be as tools for solving application problems.3) In the area of privacy-preserving association rules mining, we design a protocol for privacy-preserving quantitative association rules mining, which protect private information of different data owners when they jointly mine quantitative association rules, and a protocol for privacy-preserving statistical quantitative rule mining. Furthermore, we discuss the methods of preserving privacy in weighted association rule mining and association rule mining with multiple minimum supports. These protocols presented by us increase research content on privacy-preserving data mining and they are significantly for development of applications of SMC.4) In the area of privacy-preserving computation geometry, we present two new SMC protocols, one is a secure two-party protocol for computing the area of intersection of circle-circle, the other is a privacy-preserving protocol for determination of intersection of two polygons. We design above two protocols based on probabilistic algorithms and overcome the difficulty that input data is too little to preserve in privacy-preserving computation geometry. Moreover, it is a new idea for the design of secure protocol by introducing probabilistic algorithms.5) We consider practical scheme for secure query, and we describe two different schemes, one is based on SMC technology, the other is based on software security. Furthermore, we analyze the advantages and disadvantages of two schemes. This work is useful for developing practical systems based on SMC technology.