nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Private Subgraph Matching Protocol

verfasst von : Zifeng Xu, Fucai Zhou, Yuxi Li, Jian Xu, Qiang Wang

Erschienen in: Provable Security

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Mergeable Functional Encryption

Nächstes Kapitel A New Blockchain-Based Value-Added Tax System

Ullmann, J.R.: An algorithm for subgraph isomorphism. J. ACM (JACM) 23(1), 31–42 (1976)MathSciNetCrossRef

Solnon, C.: All different-based filtering for subgraph isomorphism. Artif. Intell. 174(12–13), 850–864 (2010)MathSciNetCrossRefMATH

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)CrossRef

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)CrossRef

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)CrossRef

Messmer, B.T., Bunke, H.: Efficient subgraph isomorphism detection: a decomposition approach. IEEE Trans. Knowl. Data Eng. 12(2), 307–323 (2000)CrossRef

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)CrossRef

Bonnici, V., Giugno, R., Pulvirenti, A., et al.: A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinform. 14(7), S13 (2013)CrossRef

10.

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)CrossRef

11.

Koyutrk, M., Grama, A., Szpankowski, W.: An efficient algorithm for detecting frequent subgraphs in biological networks. Bioinformatics 20(Suppl. 1), i200–i207 (2004)CrossRef

12.

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)CrossRef

13.

Wong, E.K.: Model matching in robot vision by subgraph isomorphism. Pattern Recogn. 25(3), 287–303 (1992)CrossRef

14.

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)CrossRef

15.

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 CrossRef

16.

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)

17.

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)

18.

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 EndowmentCrossRef

19.

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 CrossRef

20.

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)

21.

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)

22.

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 CrossRef

23.

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

24.

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 CrossRef

Titel: Private Subgraph Matching Protocol
verfasst von: Zifeng Xu
Fucai Zhou
Yuxi Li
Jian Xu
Qiang Wang
Verlag: Springer International Publishing
Buch: Provable Security
Print ISBN: 978-3-319-68636-3

Electronic ISBN: 978-3-319-68637-0

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-68637-0_27

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"