Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / protected database search; secret sharing; secure multiparty computation; oblivious filter

Date: received 13 Nov 2020

Contact author: shanzhu cjm at antgroup com,chaochao ccc@antfin com

Available format(s): PDF | BibTeX Citation

Version: 20201115:073602 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]