PGAS: Privacy-Preserving Graph Encryption for Accurate Constrained Shortest Distance Queries

Abstract The constrained shortest distance (CSD) query is used to determine the shortest distance between two vertices of a graph while ensuring that the total cost remains lower than a given threshold. The virtually unlimited storage and processing capabilities of cloud computing have enabled the graph owners to outsource their graph data to cloud servers. However, it may introduce privacy challenges that are difficult to address. In recent years, some relevant schemes that support the shortest distance query on the encrypted graph have been proposed. Unfortunately, some of them have unacceptable query accuracy, and some of them leak sensitive information that jeopardizes the graph privacy. In this work, we propose Privacy-preserving Graph encryption for Accurate constrained Shortest distance queries, called PGAS. This solution is capable of providing accurate CSD queries and ensures the privacy of the graph data. Besides, we also propose a secure integer comparison protocol and a secure minimum value protocol that realize two kinds of operations on encrypted integers. We provide theoretical security analysis to prove that PGAS achieves CQA-2 Security with less privacy leakage. In addition, the performance analysis and experimental evaluation based on real-world dataset show that PGAS achieves 100% accuracy with acceptable efficiency.