Toward Secure Trajectory Similarity Range Query Under Multiuser Setting

The widespread availability of similarity queries over trajectory data has led to numerous real-world applications, such as traffic management and path planning. With the proliferation of trajectory data, data owners often outsource storage and computation tasks to the cloud due to limited computing and storage resources. However, this scenario raises sharp security concerns, where it is critical to ensure both the integrity of query results and privacy during query processing. Furthermore, most existing works assume a single-user setting where all query users share the same key, which may lead to query privacy leakage. Therefore, in this article, we take the first step in studying the issue of multiuser and secure trajectory similarity range query (MSRQ). Specifically, inspired by the M-tree, we propose a secure index based on a distributed two-trapdoor public-key cryptosystem (DT-PKC), called M*-tree, and devise secure protocols to support multiuser query processing. We also carefully design a filtering strategy and verification scheme to ensure fast search and integrity guarantees. Finally, we theoretically analyze the security and complexity and empirically evaluate the performance and feasibility of our proposed approach.