Abstract
Graphs have more expressive power and are widely researched in various search demand scenarios, compared with traditional relational and XML models. Today, many graph search services have been deployed on a third-party server, which can alleviate users from the burdens of maintaining large-scale graphs and huge computation costs. Nevertheless, outsourcing graph search services to the third-party server may invade users’ privacy. PeGraph was recently proposed to achieve the encrypted search over the social graph. The main idea of PeGraph is to maintain two data structures XSet and TSet motivated by the OXT technology to support encrypted conductive search. However, PeGraph still has some limitations. First, PeGraph suffers from high communication and computation costs in search operations. Second, PeGraph cannot support encrypted search over dynamic graphs. In this paper, we propose an SGX-based efficient and confidentiality-preserving graph search scheme SecGraph that can support insertion and deletion operations. We first design a new proxy-token generation method to reduce the communication cost. Then, we design an LDCF-encoded XSet based on the Logarithmic Dynamic Cuckoo Filter to reduce the computation cost. Finally, we design a new dynamic version of TSet named Twin-TSet to enable encrypted search over dynamic graphs. We have demonstrated the confidentiality preservation property of SecGraph through rigorous security analysis. Experiment results show that SecGraph yields up to 208\(\times \) improvement in search time compared with PeGraph and the communication cost in PeGraph is up to 540\(\times \) larger than that in SecGraph.
The first two authors contributed equally and share the “co-first author” status. This work was supported in part by the National Natural Science Foundation of China under Grant 62172328, Natural Science Basic Research Program of Shaanxi(Program No.2024JC-JCQN-67), the Shaanxi Province QinChuangYuan "Scientist + Engineer" Team Building Project No. 2022KXJ-054, and Fundamental Research Funds for the Central Universities (xzy012022083 and xxj032022012).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In this paper, we assume that the search keywords count issued by a client is n in the form of \(w_1 \wedge ... \wedge w_n\) and \(w_1\) is the least frequent unless otherwise specified.
- 2.
Forward security refers to newly inserted data is no longer linkable to searches issued before, and backward security refers to deleted data is no longer searchable in searches issued later [13].
- 3.
Our code: https://github.com/XJTUOSV-SSEer/SecGraph.
- 4.
The code of LDCF: https://github.com/CGCL-codes/LDCF.
References
Facebook. http://www.facebook.com
Instagram. https://www.instagram.com/
Cash, D., Jaeger, J., Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M., Steiner, M.: Dynamic searchable encryption in very-large databases: Data structures and implementation. In: NDSS (2014)
Cash, D., Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M., Steiner, M.: Highly-scalable searchable symmetric encryption with support for boolean queries. In: CRYPTO. pp. 353–373 (2013)
Chase, M., Kamara, S.: Structured encryption and controlled disclosure. In: ASIACRYPT. pp. 577–594 (2010)
Chen, X., Huo, H., Huan, J., Vitter, J.S., Zheng, W., Zou, L.: Msq-index: A succinct index for fast graph similarity search. IEEE TKDE. 33(6), 2654–2668 (2021)
Costan, V., Devadas, S.: Intel sgx explained. In: Cryptology ePrint Archive (2016)
Demmler, D., Schneider, T., Zohner, M.: ABY - A framework for efficient mixed-protocol secure two-party computation. In: NDSS (2015)
Fan, B., Andersen, D.G., Kaminsky, M., Mitzenmacher, M.: Cuckoo filter: Practically better than bloom. In: CoNEXT. pp. 75–88. ACM (2014)
Gao, C., Wang, X., He, X., Li, Y.: Graph neural networks for recommender system. In: WSDM. pp. 1623–1625 (2022)
Ghosh, E., Kamara, S., Tamassia, R.: Efficient graph encryption scheme for shortest path queries. In: CCS. pp. 516–525 (2021)
Lai, S., Yuan, X., Sun, S., Liu, J.K., Liu, Y., Liu, D.: Graphse\({^2}\): An encrypted graph database for privacy-preserving social search. In: AsiaCCS. pp. 41–54 (2019)
Patranabis, S., Mukhopadhyay, D.: Forward and backward private conjunctive searchable symmetric encryption. In: NDSS (2021)
Shen, M., Wang, M., Xu, K., Zhu, L.: Privacy-preserving approximate top-k nearest keyword queries over encrypted graphs. In: IWQOS. pp. 1–10 (2021)
Wang, H., Zhao, Z., Yang, K., Song, H., Xiao, Y.: Approximate nearest neighbor search using query-directed dense graph. In: DASFAA Workshops. pp. 429–444 (2021)
Wang, Q., Yang, X., Qi, S., Qi, Y.: Secgraph: Towards sgx-based efficient and confidentiality-preserving graph search (full version)*. CoRR abs/2403.19531 (2024)
Wang, S., Zheng, Y., Jia, X., Yi, X.: Pegraph: A system for privacy-preserving and efficient search over encrypted social graphs. IEEE TIFS. 17, 3179–3194 (2022)
Zhang, F., Chen, H., Jin, H., Reviriego, P.: The logarithmic dynamic cuckoo filter. In: IEEE ICDE. pp. 948–959 (2021)
Zhang, K., Tong, Y., Shi, Y., Zeng, Y., Xu, Y., Chen, L., Zhou, Z., Xu, K., Lv, W., Zheng, Z.: Approximate k-nearest neighbor query over spatial data federation. In: DAFSAA. pp. 351–368 (2023)
Zhao, Z., Qian, P., Yang, X., Zeng, Z., Guan, C., Leong, T.W., Li, X.: Semignn-ppi: Self-ensembling multi-graph neural network for efficient and generalizable protein-protein interaction prediction. In: IJCAI. pp. 4984–4992 (2023)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Wang, Q., Yang, X., Qi, S., Qi, Y. (2024). SecGraph: Towards SGX-based Efficient and Confidentiality-Preserving Graph Search. In: Onizuka, M., et al. Database Systems for Advanced Applications. DASFAA 2024. Lecture Notes in Computer Science, vol 14853. Springer, Singapore. https://doi.org/10.1007/978-981-97-5562-2_2
Download citation
DOI: https://doi.org/10.1007/978-981-97-5562-2_2
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-5561-5
Online ISBN: 978-981-97-5562-2
eBook Packages: Computer ScienceComputer Science (R0)