Paper 2025/590

$\mathsf{emGraph}$: Efficient Multiparty Secure Graph Computation

Abstract

Secure graph computation enables computing on graphs while hiding the graph topology as well as the associated node/edge data. This facilitates collaborative analysis among multiple data owners, who may only hold a private partial view of the global graph. Several works address this problem using the technique of secure multiparty computation (MPC) in the presence of 2 or 3 parties. However, when moving to the multiparty setting, as required for collaborative analysis among multiple data owners, these solutions are no longer scalable. This remains true with respect to the state-of-the-art framework of $$ (Koti et al., CCS 2024) as well. Specifically, $$ incurs a round complexity linear in the number of parties or data owners. This is due to its reliance on secure shuffle protocol, constituting a bottleneck in the multiparty setting. Additionally, $$ has a prohibitively expensive initialisation phase due to its reliance on secure sort, with a round complexity dependent on both the graph size and the number of parties. We propose $$, a generic framework for secure graph computation in the multiparty setting that eliminates the need of shuffle and instead, relies on a weaker primitive known as $$. Further $$ is designed to have a lightweight initialisation, that eliminates the need for sorting, making its round complexity independent of the graph size and number of parties. Unlike any of the prior works, achieving a round complexity independent of the number of parties is what makes $$ scalable. Finally, we implement and benchmark the performance of $$ for the application of PageRank computation and showcase its efficiency and scalability improvements over $$. Concretely, we witness improvements of up to $$ in runtime in comparison to state-of-the-art framework $$. Further, we observe that $$ takes under a minute to perform 10 iterations of PageRank computation on a graph of size $$ that is distributed among $$ parties/data owners, making it highly practical for secure graph computation in the multiparty setting.