Research On Secure Multi-Party Computation And Its Application

With the rapid development of information technology, we are arriving at a sharp break with the life style. Information technology is everywhere in our life now. It offers convenience, but at the same time it makes troubles to us. The troubles especial the information security has influenced the normal social stability. Inofrmation security is a big problem now.Secure multi-party computation is the combination of cryptology and distributed computation. It is a new reaserch area in information security. First of all, symmetrical cryptography and public key cryptography have made great achievements. According to the evolutionary theory, secure multi-party computation will certainly be the focus of cryptography. Secondly, as a new distributed computation technology--cloud computing is developing rapidly. We learn from the past security accidents that we should pay more attention to the security issues when a new technology appears. Recently, people have paid attention to the security of cloud computing because numbers of security accidents happened. Secure multi-party computation is a tool to enchance the security in distributed computation. The usage of secure multi-party computation to cloud computing will be meaningful. Last, secure multi-party compuatation can be wildly used to protect information in our life. For example, we can use secure multi-party compuatation to meet the secure requirements in electronic voting; we can use secure multi-party compuatation to preserve privacy in data mining. In a word, research in secure multi-party computation will be worthwhile.Many exports devote themselves to search about the definition, model, security proof theory, fairness, basic modules, application protocols, methodology and feasibility reaserch in secure multi-party computation. The main contribution of this paper is as follows:(1) Based on the security problem, communication complexity problem and the storage space problem in Asmuth-Bloom secret sharing scheme, the privacy-preserving computational problem of the simultaneous congruences was raised. This problem is a new topic in the secure multi-party scientific computation. A privacy-preserving computational protocol of the simultaneous congruences in semi-honest model was presented based on the Chinese remainder theorem, the ElGamal homomorphic encryption and secure multi-party sum computation. The correctness, security and complexity of the protocol were analyzed. A multi-secret sharing scheme was also proposed based on the privacy-preserving computational protocol of the simultaneous congruences. It was proved that the new multi-secret sharing scheme solved the problems in Asmuth-Bloom secret sharing scheme. The relationship between secret sharing and secure multi-party computation is developed further in the paper.(2) The votes of losing candidates should be protected as their privacy. Meanwhile, to prevent malicious analyses, the votes of winners should also be protected. We proposed the concept of multi-privacy, which means protecting the votes of all candidates. A new electronic voting model described in three dimensions was designed. A secure multi-party data ranking protocol was proposed based on ElGamal encryption and Mix-Match network, and then a multi-privacy preserving electronic voting scheme was proposed. To solve the lack of computation resources in large-sacle electronic voting, a privacy preserving electronic voting scheme was proposed based on secure multi-party cloud computation.(3) Secure multi-party computational geometry was researched.The existing secure two party intersect-determination schemes of line segments cannot output the exact coordinates of the intersection. To solve this problem, a secure two-party line segments intersection protocol based on Paillier homomorphic encryption scheme was proposed. The security of the protocol was demonstrated using Goldreich method. The results showed that this protocol has better efficiency than the existing ones. The secure two-party line segments intersection in malicious model was also designed. As an application, we proposed a privacy-preserving convex hull intersection protocol based on the O’Rourke scheme. This application maked up for the deficiency of privacy-preserving convex hull intersection protocol in the area of secure multi-party computational geometry. The complexity of the existing privacy-preserving point inclusion protocols was related to the vertex number or the side’s number of the convex hull. The complexity will be high when the vertex number or the side’s number is large. To solve this problem, a new privacy-preserving point-inclusion protocol was proposed based on the Paillier homomorphic encryption scheme and the privacy-preserving cross products protocol for a point with a line. The security of the protocol was demonstrated using Goldreich method. As an application, we proposed a secure two party convex hull protocol base on the incremental method. The results showd that the complexity of this protocol was only related to the size of the points in the outermost layer and it had better efficiency than the existing protocols when the size of the two points’sets were large and the outermost layer’s points were few.