VPCS: Verifiable Query Scheme for Privacy-preserving Constrained Shortest Path over Encrypted Graph Data
Shiyun He, Hongfa Ding, Tian Tian, Hai Liu, Heling Jiang · 2024
Currently, massive graph data, including social networks and biological proteins, is extensively utilized and contains a substantial amount of sensitive information. As cloud computing advances, graph data owners are increasingly inclined to outsource their large-scale graph data to cloud servers for diverse graph data query services. However, the seemingly limitless storage and computing capabilities present both opportunities and privacy challenges that are difficult to address. Recent research has proposed various schemes for querying outsourced graph data in an encrypted state. Unfortunately, many of these schemes fail to guarantee the correctness of query results under malicious models and may inadvertently disclose sensitive information within the graph data. Constrained shortest path (CSP) queries aim to find the shortest path between two vertices while adhering to specific threshold constraints. In this work, we propose a robust verifiable query scheme called VPCS that ensures privacy-preserving CSP queries on encrypted graphs. Our scheme achieves accurate and verifiable results while protecting the privacy of critical graph data information, with the exception of the number of vertices. Extensive experiments using real-world data sets validate the effectiveness of our scheme.