跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 ObliGraph\mathsf{ObliGraph}, the first oblivious graph search framework that supports multiple classes of graph pattern queries under two privacy modes: FOS\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; DOS\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 ObliGraph\mathsf{ObliGraph} efficiently supports a range of graph pattern queries, achieving substantial improvements while preserving strong privacy guarantees.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 ObliGraph\mathsf{ObliGraph}, the first oblivious graph search framework that supports multiple classes of graph pattern queries under two privacy modes: FOS\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; DOS\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 ObliGraph\mathsf{ObliGraph} efficiently supports a range of graph pattern queries, achieving substantial improvements while preserving strong privacy guarantees.

查看此版本解读 →查看此版本原文 ↗