Towards Efficient Privacy-Preserving Top-k Trajectory Similarity Query

Similarity search for trajectories, especially the top-k similarity query, has been widely used in different fields, such as personalized travel route recommendation, car pooling, etc. Previous works have studied top-k similarity trajectory query in plaintext, but the increasing attention to privacy protection makes top-k similarity query on trajectory data become a challenge. In this paper, we propose a privacy-preserving top-k similarity query scheme over large-scale trajectory data based on Hilbert curve and homomorphic encryption. Towards this end, we first define a spatio-temporal trajectory similarity measure that supports homomorphic computation under ciphertext based on numerical integration algorithm for discrete trajectory data. A new filter-and-refine strategy for similarity query is also proposed to filter out the dissimilar trajectories based on Hilbert curve and refine the remaining trajectories with a secure average comparison protocol over the encrypted data. Finally, the exact query results can be obtained through Hilbert curve decoding. Our security analysis demonstrates that both locations and identities of the queried trajectories are preserved from the inference attack, and so does the privacy of the query user's trajectory. Meanwhile, extensive experimental results show that the proposed scheme can filter out 95% dissimilar trajectories with over 99% average precision, achieving higher query efficiency than the state-of-the-art techniques.