Abstract
In many applications, information can be stored and managed using graph data structures, and there is a rich set of graph algorithms that can be used to solve different problems. The subgraph isomorphism problem is defined as, given two graphs G and H, whether G contains a subgraph that is isomorphic to H. The problem has been well studied for many years, and it can be used for many application areas, such as cheminformatics, pattern matching, data mining and image processing. In this paper, we present a private subgraph matching protocol, which solves a special case of the subgraph isomorphism problem. The protocol allows two parties, each holding a private graph, to jointly compute whether one graph is a subgraph of the other. During the protocol, each party learns no useful information about the graph of the other party. We prove that the protocol is secure in the semi-honest setting.
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
References
Ullmann, J.R.: An algorithm for subgraph isomorphism. J. ACM (JACM) 23(1), 31–42 (1976)
Solnon, C.: All different-based filtering for subgraph isomorphism. Artif. Intell. 174(12–13), 850–864 (2010)
Cordella, L.P., Foggia, P., Sansone, C., et al.: A (sub) graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10), 1367–1372 (2004)
Messmer, B.T., Bunke, H.: A new algorithm for error-tolerant subgraph isomorphism detection. IEEE Trans. Pattern Anal. Mach. Intell. 20(5), 493–504 (1998)
Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. In: SODA 1995, pp. 632–640 (1995)
Shang, H., Zhang, Y., Lin, X., et al.: Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proc. VLDB Endowment 1(1), 364–375 (2008)
Messmer, B.T., Bunke, H.: Efficient subgraph isomorphism detection: a decomposition approach. IEEE Trans. Knowl. Data Eng. 12(2), 307–323 (2000)
Raymond, J.W., Willett, P.: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J. Comput. Aided Mol. Des. 16(7), 521–533 (2002)
Bonnici, V., Giugno, R., Pulvirenti, A., et al.: A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinform. 14(7), S13 (2013)
Ehrlich, H.C., Rarey, M.: Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review. Wiley Interdiscip. Rev. Comput. Mol. Sci. 1(1), 68–79 (2011)
Koyutrk, M., Grama, A., Szpankowski, W.: An efficient algorithm for detecting frequent subgraphs in biological networks. Bioinformatics 20(Suppl. 1), i200–i207 (2004)
Artymiuk, P.J., Grindley, H.M., Poirrette, A.R., et al.: Identification of beta-sheet motifs, of psi-loops, and of patterns of amino acid residues in three-dimensional protein structures using a subgraph-isomorphism algorithm. J. Chem. Inf. Comput. Sci. 34(1), 54–62 (1994)
Wong, E.K.: Model matching in robot vision by subgraph isomorphism. Pattern Recogn. 25(3), 287–303 (1992)
Llads, J., Mart, E., Villanueva, J.J.: Symbol recognition by error-tolerant subgraph matching between region adjacency graphs. IEEE Trans. Pattern Anal. Mach. Intell. 23(10), 1137–1143 (2001)
Zhu, K., Zhang, Y., Lin, X., Zhu, G., Wang, W.: NOVA: a novel and efficient framework for finding subgraph isomorphism mappings in large graphs. In: Kitagawa, H., Ishikawa, Y., Li, Q., Watanabe, C. (eds.) DASFAA 2010. LNCS, vol. 5981, pp. 140–154. Springer, Heidelberg (2010). doi:10.1007/978-3-642-12026-8_13
Han, W.S., Lee, J., Lee, J.H.: Turbo ISO: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 337–348. ACM (2013)
Foggia, P., Sansone, C., Vento, M.: A performance comparison of five algorithms for graph isomorphism. In: Proceedings of the 3rd IAPR TC-15 Workshop on Graph-Based Representations in Pattern Recognition, pp. 188–199 (2001)
Lee, J., Han, W.S., Kasperovics, R., et al.: An in-depth comparison of subgraph isomorphism algorithms in graph databases. Proc. VLDB Endowment 6(2), 133–144 (2012). VLDB Endowment
Brickell, J., Shmatikov, V.: Privacy-preserving graph algorithms in the semi-honest model. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 236–252. Springer, Heidelberg (2005). doi:10.1007/11593447_13
Cao, N., Yang, Z., Wang, C., et al.: Privacy-preserving query over encrypted graph-structured data in cloud computing. In: 2011 31st International Conference on Distributed Computing Systems (ICDCS), pp. 393–402. IEEE (2011)
Meng, X., Kamara, S., Nissim, K., et al.: GRECS: graph encryption for approximate shortest distance queries. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 504–517. ACM (2015)
Chase, M., Kamara, S.: Structured encryption and controlled disclosure. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 577–594. Springer, Heidelberg (2010). doi:10.1007/978-3-642-17373-8_33
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). doi:10.1007/3-540-48910-X_16
Kissner, L., Song, D.: Privacy-preserving set operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005). doi:10.1007/11535218_15
Acknowledgements
This work was supported in part by the National Science and Technology Major Project under Grant No. 2013ZX03002006, the Liaoning Province Science and Technology Projects under Grant No. 2013217004, the Liaoning Province Doctor Startup Fund under Grant No. 20141012, the Fundamental Research Funds for the Central Universities under Grant Numbers N130317002, N151704002, the Shenyang Province Science and Technology Projects under Grant No. F14-231-1-08, and the National Natural Science Foundation of China under Grant Numbers 61272546, 61321491, 61402095, 61472184.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Xu, Z., Zhou, F., Li, Y., Xu, J., Wang, Q. (2017). Private Subgraph Matching Protocol. In: Okamoto, T., Yu, Y., Au, M., Li, Y. (eds) Provable Security. ProvSec 2017. Lecture Notes in Computer Science(), vol 10592. Springer, Cham. https://doi.org/10.1007/978-3-319-68637-0_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-68637-0_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68636-3
Online ISBN: 978-3-319-68637-0
eBook Packages: Computer ScienceComputer Science (R0)