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
-
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},
note = {\url{https://eprint.iacr.org/2020/1415}},
url = {https://eprint.iacr.org/2020/1415}
}
