Paper 2020/1415

Secure Graph Database Search with Oblivious Filter

Jamie Cui, Chaochao Chen, Alex X. Liu, 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 work has shown interests in graph databases. In this paper, we first investigate and summarize 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 formalize the problem of OF and present its constructions using homomorphic encryption. Finally, we conduct an empirical study to evaluate the efficiency of our proposed OF protocol.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Secure Graph Database SearchSecret SharingMulti-Party ComputationOblivious Filter
Contact author(s)
shanzhu cjm @ antgroup com
chaochao ccc @ antfin com
History
2021-03-17: revised
2020-11-15: received
See all versions
Short URL
https://ia.cr/2020/1415
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1415,
      author = {Jamie Cui and Chaochao Chen and Alex X.  Liu and Li Wang},
      title = {Secure Graph Database Search with Oblivious Filter},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1415},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1415}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.