Signature-Based Secure Trajectory Similarity Search
Yiping Teng, Zhan Shi, Fanyou Zhao, Guohui Ding, Li Yuan Xu, Chunlong Fan · 2021 IEEE 20th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · 2021
In recent years, the computation and processing of trajectories have attracted both academic and industrial communities to study and develop techniques and applications due to the popularization of mobile devices. To offload the data management, it is motivated to outsource the trajectory data to the cloud for achieving great cost savings and flexibility. However, directly outsourcing trajectory data may arise serious privacy concerns. To address the problem, we define the problem of the secure trajectory similarity search over encrypted trajectory data and propose a secure trajectory similarity search approach based on a bi-directional similarity measurement. In this approach, we first propose a secure squared point to line-segment distance computation protocol to facilitate the precious and secure trajectory similarity computations. Furthermore, to improve the search performance, we propose a secure trajectory filtering method based on signature matching to filter out the dissimilar trajectories before the expensive computations on the ciphertext. Based on the proposed protocols and methods, we present a signature-based secure trajectory similarity search processing algorithm to retrieve the similarity results without revealing information about the trajectories. Finally, we theoretically analyze the computational complexity and security guarantees of the proposed approach and conduct extensive experiments on both real and synthetic datasets to test the search performance under various experimental settings.