Private Trajectory Intersection Testing: Is Garbled Circuit Better than Custom Protocols?

In this paper, two protocols are presented for private intersection detection of two moving objects’ trajectories. to design the first protocol, we simplify the problem of finding the intersection points to the problem of finding the common roots of the polynomials, which represent the moving objects’ trajectories. thereafter, gröbner basis is used to design a novel secure protocol to find the common roots of the polynomials. another protocol is also designed based on the distance computation of two trajectories’ curves. the complexity of the gröbner-based protocol for finding the common roots of polynomials is numerical. its complexity is much lower than the complexity of the garbled circuit-based protocol for euclidean distance computation of l points and the complexity of the protocols for private proximity testing