Paper 2025/1209

RingSG: Optimal Secure Vertex-Centric Computation for Collaborative Graph Processing

Zhenhua Zou, Tsinghua University
Zhuotao Liu, Tsinghua University, State Key Laboratory of Internet Architecture
Jinyong Shan, Beijing Smartchip Microelectronics Technology Co., Ltd.
Qi Li, Tsinghua University, State Key Laboratory of Internet Architecture
Ke Xu, Tsinghua University, State Key Laboratory of Internet Architecture
Mingwei Xu, Tsinghua University, State Key Laboratory of Internet Architecture
Abstract

Collaborative graph processing refers to the joint analysis of inter-connected graphs held by multiple graph owners. To honor data privacy and support various graph processing algorithms, existing approaches employ secure multi-party computation (MPC) protocols to express the vertex-centric abstraction. Yet, due to certain computation-intensive cryptography constructions, state-of-the-art (SOTA) approaches are asymptotically suboptimal, imposing significant overheads in terms of computation and communication. In this paper, we present RingSG, the first system to attain optimal communication/computation complexity within the MPC-based vertex-centric abstraction for collaborative graph processing. This optimal complexity is attributed to Ring-ScatterGather, a novel computation paradigm that can avoid exceedingly expensive cryptography operations (e.g., oblivious sort), and simultaneously ensure the overall workload can be optimally decomposed into parallelizable and mutually exclusive MPC tasks. Within Ring-ScatterGather, RingSG improves the concrete runtime efficiency by incorporating 3-party secure computation via share conversion, and optimizing the most cost-heavy part using a novel oblivious group aggregation protocol. Finally, unlike prior approaches, we instantiate RingSG into two end-to-end applications to effectively obtain application-specific results from the protocol outputs in a privacy-preserving manner. We developed a prototype of RingSG and extensively evaluated it across various graph collaboration settings, including different graph sizes, numbers of parties, and average vertex degrees. The results show RingSG reduces the system running time of SOTA approaches by up to 15.34× and per-party communication by up to 10.36×. Notably, RingSG excels in processing sparse global graphs collectively held by more parties, consistent with our theoretical cost analysis.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM CCS 2025
Keywords
Collaborative Graph ProcessingSecure Multi-party ComputationVertex-Centric Computation
Contact author(s)
zou-zh21 @ mails tsinghua edu cn
zhuotaoliu @ tsinghua edu cn
shanjinyong @ sgchip sgcc com cn
qli01 @ tsinghua edu cn
xuke @ tsinghua edu cn
xumw @ tsinghua edu cn
History
2025-06-30: revised
2025-06-28: received
See all versions
Short URL
https://ia.cr/2025/1209
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/1209,
      author = {Zhenhua Zou and Zhuotao Liu and Jinyong Shan and Qi Li and Ke Xu and Mingwei Xu},
      title = {{RingSG}: Optimal Secure Vertex-Centric Computation for Collaborative Graph Processing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1209},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1209}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.