WPEC 2024 Talk 3a4: Graphiti: Secure Graph Computation Made More Scalable

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 10⁷. Concretely, it improves over the Araki et al. (CCS'21) by up to a factor of 964x in online run time.

Joint work with: Nishat Koti, Varsha Bhat Kukkala, Arpita Patra

[Slides]