← 研踪 PaperTrailarXiv:2611.25405 · v1
ObliGraph: Graph Pattern Query Processing with Full and Differential Obliviousness
首次提交 2026-11-19 10:48
版本更新 2026-11-19 10:48
雷达观测 2026-11-20 10:50
摘要
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 , the first oblivious graph search framework that supports multiple classes of graph pattern queries under two privacy modes: achieves full obliviousness by uniformly evaluating candidate mappings, making the server-side access pattern independent of the structures of the query and data graphs; 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 efficiently supports a range of graph pattern queries, achieving substantial improvements while preserving strong privacy guarantees.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-19 10:48 · 最新观测版本
ObliGraph: Graph Pattern Query Processing with Full and Differential Obliviousness
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 , the first oblivious graph search framework that supports multiple classes of graph pattern queries under two privacy modes: achieves full obliviousness by uniformly evaluating candidate mappings, making the server-side access pattern independent of the structures of the query and data graphs; 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 efficiently supports a range of graph pattern queries, achieving substantial improvements while preserving strong privacy guarantees.
查看此版本解读 →查看此版本原文 ↗