[Vision] Towards oblivious property graph databases

Property graph databases are widely used in applications such as social networks and fraud detection due to their ability to model relationships between entities efficiently. However, outsourcing graph data to third-party cloud providers introduces significant privacy risks, as memory access patterns and result sizes can leak sensitive information even when data is encrypted. While prior work has developed oblivious relational databases to mitigate such attacks, no existing solution supports oblivious query processing for property graphs, which pose unique challenges beyond those addressed in relational settings. We present a vision for an oblivious property graph database that supports Cypher queries on encrypted outsourced data. We envision leveraging secure hardware enclaves such as Intel SGX/TDX and AMD SEV-SNP to protect query execution while novel query processing algorithms mitigate side-channel vulnerabilities through doubly oblivious query processing schemes. Specifically, we discuss the challenges in supporting oblivious query processing algorithms for multi-hop and cyclic queries without revealing data or memory access patterns. Our work highlights a crucial gap and potential research directions in oblivious query processing for property graph databases.