Private Trajectory Intersection Detection Using Grobner Basis

In this paper, we present a secure protocol for secure obtaining the intersection of two trajectories. We assume the trajectories of moving objects can be presented with polynomial functions of time. We reduce the problem of obtaining intersection of two trajectories to the problem of obtaining commonroots of polynomials. Then, we propose a secure protocol for obtaining the common roots of two polynomials, which is based on Grobner Basis. We demonstrate the security proof of our proposed protocol based on Ideal/Real Simulation Paradigm. We also present the complexity analysis of our proposed protocol and compare its complexity by the garbled circuit-based protocol for Euclidean Distance Computation of l points.

Keywords:

Secure Multi-party Computation , Trajectory Intersection , Grobner Basis , Private Prximity Testing , Garbled Circuit