Paper 2024/642

GraphOS: Towards Oblivious Graph Processing

Javad Ghareh Chamani, Hong Kong University of Science and Technology
Ioannis Demertzis, University of California, Santa Cruz
Dimitrios Papadopoulos, Hong Kong University of Science and Technology
Charalampos Papamanthou, Yale University
Rasool Jalili, Sharif University of Technology

We propose GraphOS, a system that allows a client that owns a graph database to outsource it to an untrusted server for storage and querying. It relies on doubly-oblivious primitives and trusted hardware to achieve a very strong privacy and efficiency notion which we call oblivious graph processing: the server learns nothing besides the number of graph vertexes and edges, and for each query its type and response size. At a technical level, GraphOS stores the graph on a doubly-oblivious data structure, so that all vertex/edge accesses are indistinguishable. For this purpose, we propose Omix++, a novel doubly-oblivious map that outperforms the previous state of the art by up to 34×, and may be of independent interest. Moreover, to avoid any leakage from CPU instruction fetching during query evaluation, we propose algorithms for four fundamental graph queries (BFS/DFS traversal, minimum spanning tree, and single-source shortest paths) that have a fixed execution trace, i.e., the sequence of executed operations is independent of the input. By combining these techniques, we eliminate all information that a hardware adversary observing the memory access pattern within the protected enclave can infer. We benchmarked GraphOS against the best existing solution, based on oblivious relational DBMS(translating graph queries to relational operators). GraphOS is not only significantly more performant (by up to two orders of magnitude for our tested graphs) but it eliminates leakage related to the graph topology that is practically inherent when a relational DBMS is used unless all operations are “padded” to the worst case.

Note: This is the extended version of the VLDB 2024 paper

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. VLDB 2024
Oblivious Graph ComputationDoubly Oblivious OMAPTrusted Hardware
Contact author(s)
jgc @ cse ust hk
idemertz @ ucsc edu
dipapado @ cse ust hk
charalampos papamanthou @ yale edu
jalili @ sharif edu
2024-04-29: approved
2024-04-26: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-NoDerivs


      author = {Javad Ghareh Chamani and Ioannis Demertzis and Dimitrios Papadopoulos and Charalampos Papamanthou and Rasool Jalili},
      title = {{GraphOS}: Towards Oblivious Graph Processing},
      howpublished = {Cryptology ePrint Archive, Paper 2024/642},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.