Achieving Privacy-Preserving Discrete Frechet Distance Range Queries

The advances in Internet of Things, Big Data, and machine learning technologies have greatly transformed our daily lives into much more intelligent ones by offering various promising services. Among those services, the discrete Frechet distance (DFD) range query, which aims to obtain a set of trajectories whose distances to a given query trajectory do not exceed a given threshold, has been widely applied to support applications such as vehicle trajectory clustering and other data processing tasks. Meanwhile, due to the huge data volume issue in the Big Data era, there is a trend towards outsourcing various query services to the cloud for achieving a better performance. However, since the cloud is not fully trustable, designing privacy-preserving query services becomes a research focus. Over the past years, many schemes focusing on privacy-preserving trajectory analysis have been proposed, but none of them can well support privacy-preserving DFD range queries. Aiming at addressing this challenge, this paper proposes a novel privacy-preserving DFD range query scheme, in which queries are conducted in a filtration-and-verification manner and the privacy of the dataset and queries can be preserved. Specifically, by indexing the dataset with two R-trees, a query can be conducted by i) querying the two R-trees to obtain a candidate set and ii) verifying each trajectory in the set, which involve two basic operations, namely, rectangle intersection detection and proximity detection. To preserve the privacy of the dataset and queries, we build the two basic operations upon a novel Inner-Product Preserving Encryption (IPPE) scheme, which is proved to be selectively secure with trivial leakages. Besides, extensive experiments are conducted, and the results demonstrate that our proposed scheme can significantly reduce the computational cost by effectively reducing the candidate set's size.