Study On Special Secure Multi-Party Computation Protocols

The development of the Internet opens up a mass of opportunities for cooperative computation, where the answer depends on the private inputs of separate users. The problem is trivial if the context allows the conduct of these computations by a trusted party, who computes the required function on these inputs and gives back the output to each party; however, it is difficult to find such a trusted party in the real world. If the context disallows this then the techniques of Secure Multi-party Computation become very relevant.The problem which Secure Multi-party Computation protocol solves can be described as follows: P={P₁ ,P₂ ,...,P_n } is a set of n participants, they want to securely compute a given function f ( x₁ , x₂ ,..., x_n ) = ( y₁ , y₂,..., y_n)by transmission of information each other. The n inputs of function f are provided by n participants separately. Requring P₁ ,P₂ ,...,P_n obtain y₁ , y₂,..., y_n separately after computation, security mainly means that P_i ( i = 1, 2,..., n)can not get anything about information x_j and y_j ( j = 1,2,..., i - 1, i + 1,..., n)except the information implied by xi and yi .In the past 30 years, there were large parts of the works focusing on solving general function, viz., Generic Secure Multi-party Computation, which enriched the theory to the most extreme. However, these solutions are many a time practically infeasible, motivated from this, many cryptographists in international and internal were initiated to find feasible solution to specific problems, namely Special Secure Multi-party Computation.This paper study two Special Secure Multi-party Computation protocols---privately compare information protocol and secure convex hull protocol, the main contribution are as follows:1. The security definition of privately compare information protocol with an obvious third party is given. We anlyse the correctness and privacy of the protocol which based onφ-hinding assumption and homomorphic encryption, and propose an efficient protocol based on symmetric encryption. Communication complexity, computational complexity, and security of the protocol based onφ-hinding assumption and homomorphic encryption and the protocol based on symmetric encryption were analyzed and compared, and obtain: the fomer is more theoretical while the latter is more practical;2. Wang design two protocols based on Gift Wrapping Method and Quick Hull Method separately for the first time. The paper points out the error in Quick Hull Method protocol, and proposes two improved protocols in a progressive manner. We analysis and compare the security and complexity of the Gift Wrapping protocol and those two improved protocols, and obtain: the efficiency of the improved protocolⅠis superior to the Gift Wrapping protocol; the efficiency of the improved protocolⅡi s superior to the other two protocols in general case (the number of points in the convex hull boundary is much greater than the number of points known);3. The improved protocolⅡis base on the improved protocolⅠ, and calls the improved protocolⅠ. In essence, the improved protocolⅠis the core of the improved protocolⅡ. The paper programs the core algorithm of the improved protocolⅠ, which verifies the correctness of those two improved protocol.