Research On Two Basic Secure Multi-party Computation Problems

The problem of Secure Multi-party Computation (SMC) is first proposed by A.C.Yao. SMC problem is the problem of cooperative computation which could occur among mutually distrusted participants without leaking the privacy of parties. With the rapid development of Internet, the safety problem has become the focus of attention. So many scholars studied the problem. Many basic problems have got widespread concern, such as private comparison, oblivious transfer, point-inclusion, intersect-determination of polygons et al. But the study about secure multi-party ranking problem is little. Especially the study about privacy-preserving closest pair problem is rare. Secure multi-party ranking problem can be applied to many fields, such as auctions, commercial enterprises. Privacy-preserving closest pair problem can be applied to military (especially in space), commercial enterprises. So this thesis mainly studies secure ranking problem and privacy-preserving closest pair problem.Firstly, this thesis introduces the research background and meaning of secure ranking problem and privacy-preserving closest pair problem. It also introduces protocols which have been proposed and describes the basic knowledge, including the concepts of secure ranking problem, semi-honest model and secret comparison. This thesis describes the protocols of SMC, including secure_sum, secret comparison, oblivious transfer and distance measurement.Then, the thesis studies the secure ranking problem and improves the protocols which have existed. This thesis extends the secure_sum protocol from sigle data to more data and designs a new secure multi-party ranking protocol based on the secure_sum protocol. The security and complexity are analyzed in the semi-honest model. This thesis also proposes a new secure selection protocol based on the secure_sum protocol.Thirdly, this thesis studies the privacy-preserving closest pair problem in one space. It proposes a secure two-party ranking protocol based on secret comparison and a privacy-preserving closest pair protocol based on this secure two-party ranking protocol.Finally, the thesis extends the privacy-preserving closest pair protocol from one space to two dimensional space. This protocol is based on distance measurement and can be extended to multidimensional space.