Paper 2020/1415

Highly-Scalable Protected Graph Database Search with Oblivious Filter

Jamie Cui and Chaochao Chen and Li Wang

Abstract

With the emerging popularity of cloud computing, the problem of how to query over cryptographically-protected data has been widely studied. However, most existing works focus on querying protected relational databases, few works have shown interests in graph databases. In this paper, we first investigate and summarise two single-instruction queries, namely Graph Pattern Matching (GPM) and Graph Navigation (GN). Then we follow their design intuitions and leverage secure Multi-Party Computation (MPC) to implement their functionalities in a privacy-preserving manner. Moreover, we propose a general framework for processing multi-instruction query on secret-shared graph databases and present a novel cryptographic primitive Oblivious Filter (OF) as a core building block. Nevertheless, we formalise the problem of OF and present its constructions using homomorphic encryption. We show that with OF, our framework has sub-linear complexity and is resilient to access-pattern attacks. Finally, we conduct an empirical study to evaluate the efficiency of our proposed OF protocol.