Research On Privacy-preserving Problem Of Computational Geometry

Secure Multi-party Computation(SMC,for short)is a such issue that n participants in a mutually distrustful environment evaluate a function value corporately in such a way that each party inputs his information independently and then can obtain the right results;in addition,this procedure should guarantee on the privacy of information held by each party while no revealing any information held by others except individual input and output.Due to this reason,all privacy-preserving distributed computing can be classifed to it,such as statistical analysis,compare equal,scientific computing,computational geometry,data mining,etc.In this paper,we focus on two kinds of problems in computational geometry:geometry problem and set problem,which are studied as follows.First of all,aiming at geometric problem,we study how to determine the spatial location relationship privately.most existing schemes transform the original problem into the distance problem or the correspondingly proportional data problem,which makes the computation complexity high and the application range being limited as well as computation security relatively low.To deal with these problems,we first transform the original problem into such problem whether a point is the solution of equation or not.Based on the technique,a simple and efficient scalar product protocol is adopted by us to determine five spatial relationships:point and line,point and plane,line and line,line and plane,and plane and plane.In addition,the proposed scheme does not employ any public key encryption algorithm so as to achieve the information security.Secondly,aiming at the set problem,we study how to privately determine the set membership and how to compute cardinality set-intersection.most existing schemes transform the original problem into multiple matching searches,multiple encryption,or invocation of multiple scalar product protocol.This makes computation efficiency high.Aiming at these problems,we first design a new 0-1 coding and then combine with the homomorphic encryption in order to solve the problem of set membership.Also,we design two other new coding:0-R coding and 1-0 coding,combining the homomorphic encryption,permutation protocol and scalar product protocol,to solve the cardinality set-intersection in two different methods.One of our protocols achieves the information security because of not employing any public key encryption algorithm.Finally,the correctness,security and complexity of all protocols are analyzed theoretically,which proves that the protocol designed in this paper is highly efficient and practical.