Paper 2025/2047

Enabling Index-free Adjacency in Oblivious Graph Processing with Delayed Duplications

Xinle Cao, OceanBase, Ant Group

Adam O'Neill, University of Massachusetts Amherst

Chuanhui Yang, OceanBase, Ant Group

Abstract

Obliviousness has been regarded as an essential property in encrypted databases (EDBs) for mitigating leakage from access patterns. Yet despite decades of work, practical oblivious graph processing remains an open problem. In particular, all existing approaches fail to enable the design of index-free adjacency (IFA), i.e., each vertex preserves the physical positions of its neighbors. However, IFA has been widely recognized as necessary for efficient graph processing and is fundamental in native graph databases (e.g., Neo4j). In this work, we propose a core technique named delayed duplication to resolve the conflict between IFA and obliviousness. To the best of our knowledge, we are the first to address this conflict with both practicality and strict security. Based on the new technique, we utilize elaborate data structures to develop a new EDB named Grove for processing expressive graph queries. The experimental results demonstrate that incorporating IFA makes Grove impressively outperform the state-of-the-art work across multiple graph-processing tasks, such as the well-known neighbor query and $t$-hop query.

Note: The full version of our paper about oblivious graph processing to appear in VLDB 2026.

@misc{cryptoeprint:2025/2047,
      author = {Weiqi Feng and Xinle Cao and Adam O'Neill and Chuanhui Yang},
      title = {Enabling Index-free Adjacency in Oblivious Graph Processing with Delayed Duplications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2047},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2047}
}