Privacy-preserving reachability query over graphs with result verifiability

Reachability query is one of the most popular and fundamental operations, which answers whether two given nodes are reachable in a graph. With the continuous increase of graph scale, data owners would like to upload graphs to the cloud server to enjoy the nice computing and storage service. How to realize privacy-preserving reachability query over graphs has become an important problem. Although there have already been some existed schemes for this problem, all of them only support the honest-but-curious model. If the cloud server returns the invalid query result, existing schemes will not work any longer. In this paper, we initiate the first study on realizing the verifiable privacy-preserving reachability query over graphs, and propose three step-by-step schemes based on the 2-hop labeling index and the MAC technology. The first proposed scheme can generate the verification tag for each pair of nodes in the index. But it leads to high communication and computation overhead. In order to address this problem, we propose the second scheme by constructing a special matrix to store the verification tag for each two nodes and their common nodes in the graph. It only returns one verification tag to the user, which requires less communication and computation overhead. Finally, we optimize the second scheme and propose the third scheme to further reduce the computation complexity. We make use of the symmetric-key primitives to secure the index, ensuring the necessary privacy with the ability of querying. The security analysis and extensive experiments show that our proposed schemes are secure and efficient.(c) 2023 Elsevier Ltd. All rights reserved.