Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Analysis of Toeplitz MDS Matrices Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Private Graph Intersection Protocol

verfasst von : Fucai Zhou, Zifeng Xu, Yuxi Li, Jian Xu, Su Peng

Erschienen in: Information Security and Privacy

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

A wide range of applications can benefit from storing and managing data as graph structures, and graph theory algorithms can be used to solve various computing problems. In this paper, we propose a secure two-party private graph intersection protocol against semi-honest servers. The protocol allows a server and a client, each holding a private graph, to jointly compute the intersection of their graphs. The protocol utilizes homomorphic encryptions and a private set intersection sub-protocol to prevent information leakage during the process. At the end of the protocol, the server learns the graph intersection, and the client learns the vertex intersection.

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 Privacy-Utility Tradeoff for Applications Using Energy Disaggregation of Smart-Meter Data
Nächstes Kapitel Computing Aggregates Over Numeric Data with Personalized Local Differential Privacy
Literatur
1.
Broder, A., Kumar, R., Maghoul, F., et al.: Graph structure in the web. Comput. Netw. 33(1), 309–320 (2000)CrossRef
2.
Kleinberg, J.M., Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.S.: The web as a graph: measurements, models, and methods. In: Asano, T., Imai, H., Lee, D.T., Nakano, S., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol. 1627, pp. 1–17. Springer, Heidelberg (1999). doi:10.​1007/​3-540-48686-0_​1 CrossRef
3.
Botafogo, R.A., Shneiderman, B.: Identifying aggregates in hypertext structures. In: Proceedings of the third Annual ACM Conference on Hypertext, pp. 63–74. ACM (1991)
4.
Zhang, B., Li, H., Liu, Y., et al.: Improving web search results using affinity graph. In: Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 504–511. ACM (2005)
5.
Page, L., Brin, S., Motwani, R., et al.: The PageRank citation ranking: Bringing order to the web. Stanford InfoLab (1999)
6.
Kacholia, V., Pandit, S., Chakrabarti, S., et al.: Bidirectional expansion for keyword search on graph databases. In: Proceedings of the 31st International Conference on Very Large Data Bases, pp. 505–516. VLDB Endowment (2005)
7.
Wang, M., Li, H., Tao, D., et al.: Multimodal graph-based reranking for web image search. IEEE Trans. Image Process. 21(11), 4649–4661 (2012)MathSciNetCrossRef
8.
Chakrabarti, S., Van den Berg, M., Dom, B.: Focused crawling: a new approach to topic-specific web resource discovery. Comput. Netw. 31(11), 1623–1640 (1999)CrossRef
9.
Cothey, V.: Web-crawling reliability. J. Am. Soc. Inform. Sci. Technol. 55(14), 1228–1238 (2004)CrossRef
10.
Pant, G., Srinivasan, P., Menczer, F.: Crawling the web. In: Web Dynamics, pp. 153–177. Springer, Berlin Heidelberg (2004)
11.
Buehrer, G., Chellapilla, K.: A scalable pattern mining approach to web graph compression with communities. In: Proceedings of the 2008 International Conference on Web Search and Data Mining, pp. 95–106. ACM (2008)
12.
Craven, M., Slattery, S., Nigam, K.: First-order learning for web mining. In: Nédellec, C., Rouveirol, C. (eds.) ECML 1998. LNCS, vol. 1398, pp. 250–255. Springer, Heidelberg (1998). doi:10.​1007/​BFb0026695 CrossRef
13.
Sharma, K., Shrivastava, G., Kumar, V.: Web mining: today and tomorrow. In: 2011 3rd International Conference on Electronics Computer Technology (ICECT), vol. 1, pp. 399–403. IEEE (2011)
14.
Pamnani, R., Web, C.P., Mining, U.: A research area in web mining. In: Proceedings of ISCET, pp. 73–77 (2010)
15.
Cha, M., Mislove, A., Gummadi, K.P.: A measurement-driven analysis of information propagation in the flickr social network. In: Proceedings of the 18th International Conference on World Wide Web, pp. 721–730. ACM (2009)
16.
Myers, S.A., Sharma, A., Gupta, P., et al.: Information network or social network?: the structure of the twitter follow graph. In: Proceedings of the 23rd International Conference on World Wide Web, pp. 493–498. ACM (2014)
17.
Carletti, V., Foggia, P., Vento, M.: Performance comparison of five exact graph matching algorithms on biological databases. In: Petrosino, A., Maddalena, L., Pala, P. (eds.) ICIAP 2013. LNCS, vol. 8158, pp. 409–417. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-41190-8_​44 CrossRef
18.
Pavlopoulos, G.A., Secrier, M., Moschopoulos, C.N., et al.: Using graph theory to analyze biological networks. Biodata Mining 4(1), 10 (2011)CrossRef
19.
Tian, Y., Mceachin, R.C., Santos, C., et al.: SAGA: a subgraph matching tool for biological graphs. Bioinformatics 23(2), 232–239 (2007)CrossRef
20.
21.
Angles, R., Gutierrez, C.: Survey of graph database models. ACM Comput. Surv. (CSUR) 40(1), 1 (2008)CrossRef
22.
Malewicz, G., Austern, M.H., Bik, A.J.C., et al.: Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp. 135–146. ACM (2010)
23.
Kyrola, A., Blelloch, G.E., GraphChi, G.C.: Large-scale graph computation on just a PC. In: OSDI, vol. 12, pp. 31–46 (2012)
24.
Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: Proceedings of 2000 IEEE Symposium on Security and Privacy, S&P 2000, pp. 44–55. IEEE (2000)
25.
Curtmola, R., Garay, J., Kamara, S., et al.: Searchable symmetric encryption: improved definitions and efficient constructions. J. Comput. Secur. 19(5), 895–934 (2011)CrossRef
26.
Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security, pp. 965–976. ACM (2012)
27.
Cash, D., Jarecki, S., Jutla, C., Krawczyk, H., Roşu, M.-C., Steiner, M.: Highly-scalable searchable symmetric encryption with support for boolean queries. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 353–373. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40041-4_​20 CrossRef
28.
Liesdonk, P., Sedghi, S., Doumen, J., Hartel, P., Jonker, W.: Computationally efficient searchable symmetric encryption. In: Jonker, W., Petković, M. (eds.) SDM 2010. LNCS, vol. 6358, pp. 87–100. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-15546-8_​7 CrossRef
29.
30.
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)
31.
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
32.
Freedman, M.J., Nissim, K., Pinkas, B.: Efficient Private Matching and Set Intersection. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-24676-3_​1 CrossRef
33.
34.
35.
Dachman-Soled, D., Malkin, T., Raykova, M., Yung, M.: Efficient robust private set intersection. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 125–142. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-01957-9_​8 CrossRef
Metadaten
Titel
Private Graph Intersection Protocol
verfasst von
Fucai Zhou
Zifeng Xu
Yuxi Li
Jian Xu
Su Peng
Copyright-Jahr
2017
Buch
Information Security and Privacy

Print ISBN: 978-3-319-59869-7

Electronic ISBN: 978-3-319-59870-3

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-59870-3_13

Premium Partner

    Bildnachweise