<i>e</i>PPTM—Enhanced Privacy-Preserving Trajectory Matching on Autonomous Vehicles

Detecting in advance spatiotemporal collisions among autonomous vehicles (AVs) is crucial for enhancing safety and reducing risks. However, comparing plain-text trajectories leaks private path information, e.g., the location of storage sites, and may reveal private users’ data. Although the literature already provides a few solutions for privacy-preserving trajectory comparison, they cannot handle sparse trajectory data, leading to increased safety risks. In this article, we propose ePPTM, an enhanced fully accurate protocol for privacy-preserving trajectory matching among AVs. ePPTM combines two main building blocks, i.e., the Incremental Capsule Matching algorithm, detecting co-location using capsules defined over trajectories at an increasing level of granularity, and privacy-preserving proximity testing, allowing comparison among trajectory identifiers by revealing only colliding elements. We describe two modes of ePPTM, i.e., the Truncated Mode and Full Mode, with the former potentially decreasing processing demands while fully preserving privacy and safety (no missed collisions). We implement a proof of concept of ePPTM, release the code open source, and test it on two testbeds involving heterogeneous devices and real sparse trajectory data. We demonstrate experimentally the perfect accuracy of ePPTM, i.e., 100% accuracy in identifying collisions, while earlier approaches simply fail. We also explore the overhead of ePPTM, showing that it is lightweight when trajectories do not collide or have only a few points in common. The overhead increases when trajectories are more similar, but can be always kept under control at the expense of a little privacy leakage.