Study On Several Special Secure Multi-Party Computation Problems

A secure multi-party computation (SMC) problem deals with computing a function on any input in a distributed network where each participant holds one of the inputs, and that no more information is revealed to a participant in the computation than can be inferred from that participant's input and output.Secure multi-party computation was firstly brought forward by A.C.Yao in 1982. Secure multi-party computation protocol is an important area in cryptography. It's the basis of many distributed cryptographic protocols, such as threshold cryptosystem, electronic voting and electronic auction etc. It is based on many basic cryptographic protocols (e.g. homomorphic encryption and zero-knowledge proof) and some basic protocols in distributed computation (e.g. oblivious transfer and broadcast protocol). Research in the SMC area has been focusing on privacy-preserving scientific computation, privacy-preserving geometric computation, privacy-preserving data mining, privacy-preserving statistical analysis etc.To sum up, the innovations of this thesis could be summarized as following:1. The theory, technique and actuality of Millionaire's problem were summarized. Based on E1 Gamal, RSA homomorphic encryption, two protocols of secure multi-party multi-data ranking problem were proposed. The problem extended Yao's Millionaires' problem. Furthermore, the correctness and security of this protocol were shown in semi-honest model, using the definition of secure multi-party computation. The solutions of secure multi-party multi-data ranking problem can form a fundamental basis of new-style electronic transaction, such as private biding and auction, secret online transaction and so on.2. The theory, technique and actuality of Socialist Millionaires' problem were summarized. And a model of sliding window was presented. A new solution to the Socialist Millionaires' Problem was proposed based on sliding window and commutation encryption function, and the security of this solution was proven based on simulator. A secure multi-party comparing protocol was proposed based on multi-threshold secret sharing scheme.3. The theory, technique and actuality of secure multi-party computation geometry problems were summarized. A protocol of privacy-preserving point-line relation determination, a study of secure two-party circule computation problem and a privacy-preserving triangle inequality determination protocol were presented. The correctness, security and efficiency of these protocols were also analyzed.4. The theory, technique and actuality of privacy-preserving data mining were summarized. A millionaires' protocol on real number background and four tools of secure two-party add-product, secure two-party add-divide, secure two-party logarithm, secure maximal sum of two components of two vectors were constructed based on secure two-party product protocol and Yao's millionaires' protocol on discrete background. A privacy-preserving choosing the attribute of maximal information gain protocol was proposed, which can be used to solve the key problem of secure decision tree construction for arbitrarily partitioned data. Using this protocol, the privacy of data owned by two parties can be preserved. The security of this protocol was proven and the computation complexity and communication complexity were analyzed based on the theory of secure multi-party computation.A new privacy preserving sequential pattern mining solution was also designed based on secure multi-party sum protocol and secure multi-party multi-data raking protocol and a simple analysis of this solution was given.