Research On Secure Multiparty Computation In Computational Geometry And Graph Theory

Nowadays,with the rapid development of information technology and network technology,digital data is generated explosively,and thus brought us into the era of big data.The development of big data makes it more and more convenient for people to collect and analyze data.It has also become a common phenomenon for different entities to share their data and conduct cooperative computation to obtain more valuable data information.But at the same time,sharing data may leak participants' private or confidential information,causing serious consequences.How to ensure the confidentiality and privacy of private data while sharing data and joint computing,so as to maximize the value of data,is an urgent problem to be solved,and secure multi-party computation(MPC)is a powerful tool to solve this problem.MPC has always been a research hotspot of cryptography and an important privacy preserving technology in the information age.Through MPC,participants can jointly compute in the mutual distrust network environment.After the computation,participants get the expected results,but they know nothing more than what they can derive from the result about other participants' information.MPC solves the problem of data privacy and security,and protects the security of private information.The current research on MPC includes scientific computation,computational geometry,statistical analysis,data mining,and other problems.In terms of computational geometry,it is an early research problem in MPC.At present,many schemes are low efficiency.At the same time,the existing MPC solutions can only compute functions of private integer data without considering private data type that describes the association between things,that is,the MPC of graph structure data.However,the study of the relationship between things and the discovery of laws are crucial to understand the nature and to reform the world.In this paper,we study some problems of computational geometry and graph in MPC in depth.The main research contents are as follows.1.For the computational geometry problem of MPC,we first study the problem of privately determining the intersection of line segments.The protocol we design can also be extended to privately determine the intersection of polygons.Then,we design a protocol to compute the distance from a point to a plane,which can not only solve the integer problem,but also solve the rational number problem.Based on the principle of computing the distance,we also solve the problem of privately determining the relationship between a line and a plane,as well as the problem of privately determining the relationship between two planes.Compared with the existing schemes,the efficiency of our protocols is greatly improved.2.For MPC of graph structure data,we study the MPC of graph intersection and union.We propose a new encoding method to represent a graph,and design protocols which can resist collusion attacks of any parties by combining the secure substitution method and threshold decryption scheme.Both theoretical analysis and experimental simulation result show that compared with the existing protocol,the computational efficiency,communication efficiency and security of our protocol are greatly improved.3.In the study of secure query on graph structure data,we propose three new problems:secure query of sub-graph,secure query of path and secure query of graph edit distance.We design three new encoding methods for these three problems,and design efficient protocols to solve these problems.