Paper 2025/2047
Enabling Index-free Adjacency in Oblivious Graph Processing with Delayed Duplications
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.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Published elsewhere. Major revision. VLDB 2026
- Keywords
- Oblivious AlgorithmsEncrypted Databases
- Contact author(s)
-
weiqifeng @ umass edu
caoxinle cxl @ antgroup com
adamoneill @ umass edu
rizhao ych @ oceanbase com - History
- 2026-04-08: last of 3 revisions
- 2025-11-05: received
- See all versions
- Short URL
- https://ia.cr/2025/2047
- License
-
CC BY-NC
BibTeX
@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}
}
