Privacy-Preserving Verifiable Graph Intersection Scheme With Cryptographic Accumulators in Social Networks

Due to wealthy structure and semantic information expressed by a graph, the graph is frequently employed in numerous social applications to show social relationships. Among those important applications, the private graph intersection operation plays an important part in social networks. Because of the high cost of managing graph data and the computational difficulty of graph intersection operation, delegating the computations to the cloud server (CS) is an attractive alternative. However, when the CS is untrusted or compromised by some adversaries, the results that the CS returns can not be guaranteed to be correct. In such cases, it may have serious consequences for the application functionality. In this article, we present an efficient and privacy-preserving verifiable graph intersection scheme with cryptographic accumulators in social networks. Using the proposed scheme, we construct the framework to provide secure verifiable graph intersection operation in an untrusted cloud, and the requester can verify the correctness of the graph intersection result that the CS returns. Additionally, the data owners' graph data privacy and user authentication are well protected. The detailed correctness proof and performance analysis show that the proposed scheme is secure and feasible. Thus, our scheme is appropriate for many practical applications.