Paper 2024/642
GraphOS: Towards Oblivious Graph Processing
Abstract
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
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. VLDB 2024
- Keywords
- 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 - History
- 2024-04-29: approved
- 2024-04-26: received
- See all versions
- Short URL
- https://ia.cr/2024/642
- License
-
CC BY-NC-ND
BibTeX
@misc{cryptoeprint:2024/642,
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{https://eprint.iacr.org/2024/642}},
url = {https://eprint.iacr.org/2024/642}
}
