Privacy-preserving label-constrained reachability queries for large graphs in cloud environments

Abstract As real-world networks continue to evolve and expand, edge-labeled graphs have garnered attention for their capability to capture information more effectively in complex networks. To enhance the speed of queries on networks, researchers often opt to outsource complex and large amounts of network data to cloud servers. However, this approach raises concerns regarding the security and privacy of sensitive information inherent to the graph. This paper presents an innovative and practical privacy-preserving scheme for label-constrained reachability queries on edge-labeled graphs. To safeguard the privacy and security of sensitive information in the graph, we employ a range of encryption technologies to construct a secure label-constrained index. To ensure the privacy of query results, we design three functions based on symmetric homomorphic encryption. These functions effectively convert the label query problem on the index into a computational task with ciphertexts. This approach ensures the confidentiality of sensitive information while enabling efficient and accurate processing of label-constrained reachability queries. Comprehensive security analysis, complexity analysis, and simulation experiments utilizing real datasets collectively confirm the effectiveness of the proposed scheme in enabling privacy-preserving label-constrained reachability queries in cloud environments.