Paper 2025/590

$\mathsf{GraSP}$: Secure Collaborative Graph Processing Made Scalable

Nishat Koti, Aztec Labs

Varsha Bhat Kukkala, Indian Institute of Technology Tirupati

Arpita Patra, Indian Institute of Science Bangalore

Bhavish Raj Gopal, Indian Institute of Science Bangalore

Abstract

Secure graph processing 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, the existing solutions are no longer scalable. Specifically, the runtime of the state-of-the-art scales linearly with the number of parties. Additionally, it has an expensive initialisation phase, which requires secure sorting operations known to be expensive in MPC. Thus, we propose $\mathsf{GraSP}$, a generic framework for secure graph processing that improves efficiency and scalability for the multiparty setting. Further, $\mathsf{GraSP}$ is designed to have a lightweight initialisation, which eliminates the need for secure sorting. Unlike any of the prior works, achieving a round complexity in MPC that is independent of the number of parties is what makes $\mathsf{GraSP}$ scalable. Finally, we implement and benchmark the performance of $\mathsf{GraSP}$ for the application of PageRank computation and showcase its efficiency and scalability improvements over the state-of-the-art. Concretely, we witness improvements of up to $78\times$ in runtime in comparison to the state-of-the-art. Further, we observe that $\mathsf{GraSP}$ takes under a minute to perform 10 iterations of PageRank on a graph of size $10^6$ that is distributed among $25$ data owners, making it highly practical for secure graph processing in the multiparty setting.

@misc{cryptoeprint:2025/590,
      author = {Siddharth Kapoor and Nishat Koti and Varsha Bhat Kukkala and Arpita Patra and Bhavish Raj Gopal},
      title = {$\mathsf{{GraSP}}$: Secure Collaborative Graph Processing Made Scalable},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/590},
      year = {2025},
      url = {https://eprint.iacr.org/2025/590}
}