PMatch: A Secure Framework for Querying Private Localized Graph Patterns

This work studies privacy-preserving graph pattern query services in the database outsourcing paradigm. In such a paradigm, users send their queries to a third-party service provider (SP), who has the outsourced large graph data, and SP computes the query answers. However, as SP may not always be trusted, the sensitive information of the users' queries, importantly, the query structures, should be protected. This work adopts the localized graph patterns as practical query semantics for this paradigm, including subgraph homomorphism, subgraph isomorphism, and strong simulation, for which each matched graph pattern is located in a subgraph called ball that have a restriction on its size. To provide privacy-preserving query processing, we propose a general query matching framework called PMatch that not only efficiently computes approximate existence of matched patterns in the ciphertext domain with only false positives so that exact answers can be securely obtained on the user side, but also achieves high accuracy of the existence results by using pruning strategies specifically designed based on different graph structures. Extensive experiments on real-world datasets demonstrate PMatch’s efficiency and effectiveness.