A new Lagrange solution to the privacy-preserving general geometric intersection problem

Secure multi-party computation (SMC) is an important problem in cryptography. Existing solutions are mostly based on circuit evaluation protocols which are impractical. In this paper, a solution is proposed by abstracting the intersection problem and the judging private path problem into a general intersection problem, i.e., if two participants have a private curve and do not disclose their private curve data, how to solve two-free-plane-curve intersection problem in a cooperative environment. A systematic Lagrange multiplier method is proposed to combat the general intersection problem instead of focusing on normal curves case. The proposed systematic method can systematically deal with various intersection problems faced in practical applications. In addition, the proposed method can also solve the normal curves cases. This paper extend the judging private path problem to the general case.The geometry computation problems are transferred to algebraic computation problems.B spline curves are used to improve the approximation accuracy of the free curves.A systematic solution to determine whether two free curves intersect is proposed.The accuracy and efficiency are improved.