ObliGraph: Graph Pattern Query Processing with Full and Differential Obliviousness
Abstract
Graph pattern query is a fundamental primitive in graph databases for retrieving data graphs that match a query graph under various structural constraints. As graph data is increasingly outsourced to third-party cloud servers for scalable query processing, however, both the query graph and the data graphs may leak sensitive structural information through server-side access patterns. In this paper, we study privacy-preserving graph pattern query processing in the outsourced setting, aiming to protect the structures of both the query and data graphs from access-pattern leakage. To this end, we propose $\mathsf{ObliGraph}$, the first oblivious graph search framework that supports multiple classes of graph pattern queries under two privacy modes: $\mathsf{FOS}$ achieves full obliviousness by uniformly evaluating candidate mappings, making the server-side access pattern independent of the structures of the query and data graphs; $\mathsf{DOS}$ further improves query efficiency through pruning while retaining a provable privacy guarantee of differential obliviousness. This design enables a smooth trade-off between stronger privacy and higher efficiency within a single framework. Experiments on real and synthetic datasets demonstrate that $\mathsf{ObliGraph}$ efficiently supports a range of graph pattern queries, achieving substantial improvements while preserving strong privacy guarantees.