A security solution to the Points-Hyperspace Inclusion problem
Yonglong Luo, Caiyun Zhang, Lei Shi, Wenjuan Cheng · 2010
Privacy-preserving computational geometry (PPCG) is a Secure Multi-party Computation problem. Determining the relationship of a point and a hyperspace is a security of the points-range inclusion problem which is one of PPCG problems. This paper studies the special SMC protocols to solve the special computational geometry problem, uses random technology to improve efficiency, so that it can be better used in online transactions and other applications. Firstly, a protocol for the Points-Rectangle Area Inclusion problem which is based on multiplication protocol is developed. 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.