Privacy-Preserving Graph Matching Query Supporting Quick Subgraph Extraction

Abstract

Graph matching, as one of the most fundamental problems in graph database, has a wide range of applications. Due to the large scale of graph database and the hardness of graph matching, graph user tends to outsource the encrypted graphs to the cloud. The complex graph matching is performed by the cloud. Several schemes have been proposed to support graph matching query over encrypted graphs. However, none of them can realize efficient subgraph extraction when the matched subgraph needs to be exactly located at the data graph. The graph user has to perform the complex subgraph isomorphism (NP-complete problem) operation to extract the isomorphic subgraph from the matched data graph in state-of-the-art schemes. In order to solve this problem, we propose a privacy-preserving graph matching query scheme supporting quick subgraph extraction in this paper. In our design, two non-colluding cloud servers are adopted to accomplish the matching operation jointly. Neither of them can infer the plaintexts of graphs. Two cloud servers jointly get a matched matrix to represent the matching relationship between vertices in data graph and query graph. Graph user can directly and quickly extract the subgraph isomorphic to query graph from data graph based on the matched matrix. No subgraph isomorphism operation is involved for graph user. The time complexity of subgraph extraction is <inline-formula><tex-math notation="LaTeX">$O(m^{2})$</tex-math></inline-formula> in our scheme, where <inline-formula><tex-math notation="LaTeX">$m$</tex-math></inline-formula> is the number of vertices in query graph. The extensive experiments with real-world database demonstrate the efficiency of the proposed privacy-preserving graph matching scheme.