Privacy-Preserving Subgraph Matching Scheme With Authentication in Social Networks

With the popularity of social networks, a great variety of new social applications have been generated for impromptu group formation and communications. Among those applications, the subgraph matching has become a hot research area in social networks. Due to the huge cost of managing and computing graph data, it may have to outsource the computations to the cloud server. However, the most critical problem is that the cloud server leaks the graph information during the processing of the graph data, and the external attackers modify the graph information during the transmission on the public channel. Thus, confidentiality and authentication have been critical attributes in the subgraph matching query service. In this article, we present an efficient and privacy-preserving subgraph matching scheme with authentication in social networks. Using the proposed scheme, the cloud can accomplish the subgraph matching query process without obtaining any sensitive information about the users. Additionally, we achieve data integrity verification and user authentication. Each receiver can verify if the received messages come from the legal sender and have not been tampered. The detailed security and efficiency analysis show that the proposed scheme not only satisfies security requirements but also achieves high-efficiency in local users, and it is suitable for many practical applications.