Paper 2026/2550
PPGA: A Framework for Privacy-Preserving Graph Algorithms using the Prepare/Propagate/Gather/Apply Paradigm
, Technical University of Darmstadt, Technical University of DarmstadtAbstract
Privacy-preserving graph computation enables the secure analysis of graphs modeling social interactions and networks, financial transactions, etc., while keeping the graph private. One approach is to use secure multiparty computation (MPC), allowing different clients to contribute parts of a graph without need of disclosure, and multiple MPC protocols have been proposed for running message-passing-based graph analysis. Yet, existing public implementations are prototypes for fixed analysis functions that require substantial MPC expertise to modify and extend. We present PPGA, a practical framework based on the MultiCent protocol (PETS'25). PPGA lets users define their custom message-passing graph algorithms with a high-level interface, clients input parts of the graph, and then runs the algorithm in MPC. It significantly improves performance compared to MultiCent's implementation, running BFS on a graph of size |V|+|E|=30 million in 23 minutes without leaking the graph topology.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- Secure Multiparty ComputationMPCGraph AnalysisMessage-PassingFramework
- Contact author(s)
-
brueggemann @ encrypto cs tu-darmstadt de
simon brunnauer @ stud tu-darmstadt de
schneider @ encrypto cs tu-darmstadt de - History
- 2026-10-20: approved
- 2026-10-19: received
- See all versions
- Short URL
- https://ia.cr/2026/2550
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2550,
author = {Andreas Brüggemann and Simon Brunnauer and Thomas Schneider},
title = {{PPGA}: A Framework for Privacy-Preserving Graph Algorithms using the Prepare/Propagate/Gather/Apply Paradigm},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2550},
year = {2026},
url = {https://eprint.iacr.org/2026/2550}
}
