Koti, Nishat ; Kukkala, Varsha Bhat ; Patra, Arpita ; Gopal, Bhavish Raj (2024)
Graphiti: Secure Graph Computation Made More Scalable.
NIST Workshop on Privacy-Enhancing Cryptography 2024. virtual Conference (24.09.2024 - 26.09.2024)
Konferenzveröffentlichung, Bibliographie
Kurzbeschreibung (Abstract)
Graphs are fundamental tools for modelling data in diverse real-world applications such as communication networks, traffic systems, and social networks. However, graph data is often distributed across multiple data owners and contains sensitive information, posing significant privacy concerns that impede collaborative analysis. Privacy-preserving graph analysis enables computations on graphs that store sensitive information, ensuring that all information about the topology of the graph, as well as data associated with the nodes and edges, remains hidden.In this talk, we will discuss potential solutions for privacy-preserving graph analysis, with an emphasis on using secure multiparty computation (MPC). We will review existing MPC-based approaches for privacy-preserving graph analysis, identifying their limitations in terms of efficiency, scalability, and adaptability. Furthermore, we will present our results in enhancing privacy-preserving graph analysis and highlight the remaining challenges.Specifically, we will introduce our highly scalable framework, Graphiti, that can realize any graph algorithm securely. Since round complexity forms one of the key parameters in determining the efficiency of MPC protocols, one of our key technical contributions is that Graphiti has round complexity independent of the graph size, which in turn allows for attaining the desired scalability.This is in contrast to the state-of-the-art framework of GraphSC by Araki et al. (CCS'21) whose round complexity scales with the graph size. Benchmarks show that Graphiti takes less than 2 minutes for contact tracing via BFS for 10 hops when computing over a graph of size 107. Concretely, it improves over the Araki et al. (CCS'21) by up to a factor of 964x in online run time.
| Typ des Eintrags: | Konferenzveröffentlichung |
|---|---|
| Erschienen: | 2024 |
| Autor(en): | Koti, Nishat ; Kukkala, Varsha Bhat ; Patra, Arpita ; Gopal, Bhavish Raj |
| Art des Eintrags: | Bibliographie |
| Titel: | Graphiti: Secure Graph Computation Made More Scalable |
| Sprache: | Englisch |
| Publikationsjahr: | 2024 |
| Veranstaltungstitel: | NIST Workshop on Privacy-Enhancing Cryptography 2024 |
| Veranstaltungsort: | virtual Conference |
| Veranstaltungsdatum: | 24.09.2024 - 26.09.2024 |
| URL / URN: | https://csrc.nist.gov/Presentations/2024/wpec2024-3a4 |
| Kurzbeschreibung (Abstract): | Graphs are fundamental tools for modelling data in diverse real-world applications such as communication networks, traffic systems, and social networks. However, graph data is often distributed across multiple data owners and contains sensitive information, posing significant privacy concerns that impede collaborative analysis. Privacy-preserving graph analysis enables computations on graphs that store sensitive information, ensuring that all information about the topology of the graph, as well as data associated with the nodes and edges, remains hidden.In this talk, we will discuss potential solutions for privacy-preserving graph analysis, with an emphasis on using secure multiparty computation (MPC). We will review existing MPC-based approaches for privacy-preserving graph analysis, identifying their limitations in terms of efficiency, scalability, and adaptability. Furthermore, we will present our results in enhancing privacy-preserving graph analysis and highlight the remaining challenges.Specifically, we will introduce our highly scalable framework, Graphiti, that can realize any graph algorithm securely. Since round complexity forms one of the key parameters in determining the efficiency of MPC protocols, one of our key technical contributions is that Graphiti has round complexity independent of the graph size, which in turn allows for attaining the desired scalability.This is in contrast to the state-of-the-art framework of GraphSC by Araki et al. (CCS'21) whose round complexity scales with the graph size. Benchmarks show that Graphiti takes less than 2 minutes for contact tracing via BFS for 10 hops when computing over a graph of size 107. Concretely, it improves over the Araki et al. (CCS'21) by up to a factor of 964x in online run time. |
| Freie Schlagworte: | E4 |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Praktische Kryptographie und Privatheit 20 Fachbereich Informatik > Telekooperation DFG-Sonderforschungsbereiche (inkl. Transregio) DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche DFG-Graduiertenkollegs DFG-Graduiertenkollegs > Graduiertenkolleg 2050 Privacy and Trust for Mobile Users DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1119: CROSSING – Kryptographiebasierte Sicherheitslösungen als Grundlage für Vertrauen in heutigen und zukünftigen IT-Systemen |
| Hinterlegungsdatum: | 25 Okt 2024 14:31 |
| Letzte Änderung: | 25 Okt 2024 14:31 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum