Light-Weight Graph Matching Query Over Encrypted Graphs

Graph matching, as an important query technology, has been widely applied in various fields. With the increasing of graph data, users choose to encrypt a large number of graphs and store them in the cloud. Existing solutions to graph matching query over encrypted graphs require the user to execute a lot of time-consuming subgraph isomorphism (NP-complete problem) operations to extract the matched graphs, which inevitably brings heavy computational burden to the user. Therefore, how to reduce the number of subgraph isomorphisms is crucial for releasing the user from the heavy workload in a graph matching query scheme over encrypted graphs. In this paper, we propose a secure and efficient scheme for graph matching query over encrypted graphs. The main idea is to classify the query graph into frequent subgraph and infrequent subgraph, and adopt different strategies to perform the matching query. We design the novel secure index based on the frequent subgraphs and the edge labels to reduce the number of subgraph isomorphisms. When the query graph is a frequent subgraph, the proposed scheme can directly produce the exact result owing to this secure index. The user does not need to perform any subgraph isomorphism in this case. When the query graph is an infrequent subgraph, the proposed scheme can return a set of data graphs very close to the exact result. As a result, the proposed scheme reduces the number of subgraph isomorphisms substantially. Formal security proof is provided. Extensive experiments on real-world data sets show that the proposed scheme reduces nearly 90% subgraph isomorphism.