The Research On The Privacy-preserving Safety Query Problem And Its Application

Computational geometry is a study of computer algorithms to solve geometric problems. Its research result has already gotten an extensive application in the computer graphics, the chemistry, the statistics, the pattern recognition, the geographic database and other many domains. Privacy-preserving computational geometry is a special multi-party computation problem. It includes many problems, such as the point-inclusion problem, the intersect problem, the closest pair problem and the convex hulls problem. The privacy-preserving safety query problem can convert into the point-inclusion problem. In this paper, we studied the security solutions to the privacy-preserving points-range, points-rectangle area and polnts-hyperspace inclusion problems.Firstly, we studied the security solutions to the privacy-preserving points-interval inclusion problem. We developed two points-range determing protocol, which are based on comparison and Homomorphic Encryption Schemes separately, and analyse their correctness, safety arid complexity.Secondly, we studied the security solutions to the privacy-preserving points-rectangle area inclusion problem. According to the analysis of the relationship of a point and a rectangle area, we got a formula which can determine the relationship of a point and a rectangle area. Then two points-rectangle area determing protocol are developed, which are based on scalar product protocol and Multiplication Protocol separately, and analyse their correctness, safety and complexity. In the condition ofLastly, we mainly studied the security solutions to the privacy-preserving points-hyperspace inclusion problem. Then a probability algorithm for points-hyperspace inclusion problem is presented. The probability algorithm is proved that it is a true-biased Monte Carlo algorithm. Both of the theoretical analysis and the experiment results show that the probability algorithm is efficient.