Dual-Cloud Collaborative Graph Edit Distance Secure Computation Protocol

Yufeng Wang

doi:10.54097/1yzx3y42

Authors

Yufeng Wang

DOI:

https://doi.org/10.54097/1yzx3y42

Keywords:

Privacy Protection, Cloud Computing, Graph Theory, Graph Edit Distance.

Abstract

To address the challenge of securely computing graph edit distance in directed graph scenarios without compromising parties' privacy data, this paper proposes a homomorphic encryption-based, dual-cloud-assisted secure graph edit distance computation protocol. The protocol encodes graph structures as adjacency matrices and introduces random parity noise to protect the original data's parity. It then leverages homomorphic encryption to compute edit distance in ciphertext form. Employing a dual-cloud server architecture, the protocol offloads most computational tasks to the cloud, eliminating direct interaction between data users. This approach enhances computational efficiency while ensuring privacy security. Theoretical analysis and simulation experiments demonstrate the protocol's security under a semi-honest model, with superior user-side computational overhead compared to existing solutions.

References

[1] Zhao, C., Zhao, S., Zhao, M., Chen, Z., Gao, C. Z., Li, H., & Tan, Y. A. (2019). Secure multi-party computation: theory, practice and applications. Information Sciences, 476, 357-372.

[2] Goldreich, O. (1998). Secure multi-party computation. Manuscript. Preliminary version, 78(110), 1-108.

[3] Pang, H., & Wang, B. (2020). Privacy-preserving association rule mining using homomorphic encryption in a multikey environment. IEEE Systems Journal, 15(2), 3131-3141.

[4] Abawajy, J. H., Ninggal, M. I. H., & Herawan, T. (2016). Privacy preserving social network data publication. IEEE communications surveys & tutorials, 18(3), 1974-1997.

[5] Prathik, A., Uma, K., & Anuradha, J. (2016). An overview of application of graph theory. International Journal of ChemTech Research, 9(2), 242-248.

[6] Ding, X., Wang, C., Choo, K. K. R., & Jin, H. (2019). A novel privacy preserving framework for large scale graph data publishing. IEEE transactions on knowledge and data engineering, 33(2), 331-343.

[7] Arshad, M. U., Kundu, A., Bertino, E., Ghafoor, A., & Kundu, C. (2017). Efficient and scalable integrity verification of data and query results for graph databases. IEEE Transactions on Knowledge and Data Engineering, 30(5), 866-879.

[8] Liu, X., Tu, X. F., Luo, D., Xu, G., Xiong, N. N., & Chen, X. B. (2023). Secure multi-party computation of graphs’ intersection and union under the malicious model. Electronics, 12(2), 258.

[9] Wang, S., Zheng, Y., Jia, X., Huang, H., & Wang, C. (2022). OblivGM: Oblivious attributed subgraph matching as a cloud service. IEEE Transactions on Information Forensics and Security, 17, 3582-3596.

[10] Sharmila, G., & Kavitha Devi, M. K. (2024). BTLA-LSDG: Blockchain-based triune layered architecture for authenticated subgraph query search in large-scale dynamic graphs. IETE Journal of Research, 70(2), 1495-1518.

[11] Ghosh, E., Kamara, S., & Tamassia, R. (2021, May). Efficient graph encryption scheme for shortest path queries. In Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security (pp. 516-525).

[12] Zuo, X., Li, L., Peng, H., Luo, S., & Yang, Y. (2020). Privacy-preserving subgraph matching scheme with authentication in social networks. IEEE Transactions on Cloud Computing, 10(3), 2038-2049.

[13] Liu, X., Kong, J., Peng, L., Luo, D., Xu, G., Chen, X., & Liu, X. (2023). A Secure Multi-Party Computation Protocol for Graph Editing Distance against Malicious Attacks. Mathematics, 11(23), 4847.

[14] Sanfeliu, A., & Fu, K. S. (2012). A distance measure between attributed relational graphs for pattern recognition. IEEE transactions on systems, man, and cybernetics, (3), 353-362.

[15] Wei, Q., Li, S. D., Wang, W. L., & Du, R. M. (2020). Secure multi-party computation of graph intersection and union. J. Cryptologic Res, 7, 774-788.

[16] Paillier, P. (1999, April). Public-key cryptosystems based on composite degree residuosity classes. In International conference on the theory and applications of cryptographic techniques (pp. 223-238). Berlin, Heidelberg: Springer Berlin Heidelberg.

[17] Fisher, R. A., & Yates, F. (1953). Statistical tables for biological, agricultural and medical research. Hafner Publishing Company.

[18] Durstenfeld, R. (1964). Algorithm 235: random permutation. Communications of the ACM, 7(7), 420.

[19] Lindell, Y. (2017). How to simulate it–a tutorial on the simulation proof technique. Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, 277-346.

[20] Feng, D., & Yang, K. (2022). Concretely efficient secure multi-party computation protocols: survey and more. Security and Safety, 1, 2021001.

[21] Gao, W., & Yu, J. (2025). Enabling Privacy-Preserving Top-k Hamming Distance Query on the Cloud. IEEE Transactions on Network and Service Management.

[22] Ge, X., Yu, J., & Hao, R. (2023). Privacy-preserving graph matching query supporting quick subgraph extraction. IEEE Transactions on Dependable and Secure computing, 21(3), 1286-1300.