Privacy-Preserving Graph Encryption for Approximate Constrained Shortest Distance Queries

Constrained shortest distance (CSD) queries are a valuable extension of the traditional pairwise shortest distance computation over graph-structured data, where the answers to the queries should fulfill a cost constraint (e.g., the toll payment in road networks). With the popularity of cloud computing, data owners have a strong desire to migrate their privacy-sensitive graphs to remote servers without losing the ability to query them. Existing graph encryption schemes cannot provide security guarantees for CSD queries. In this paper, we present Acro, a graph encryption scheme, which executes approximate CSD queries securely. The homomorphic encryption and the symmetric-key primitives are applied to our scheme. Through a security analysis, we prove that Acro meets the security definition of CQA2-security. The prototype of Acro is implemented and evaluated using real datasets. The results show that our proposal outperforms a state-of-the-art baseline in terms of query accuracy at the cost of enlarging query completion time.