POPPY: Scalable and Secure Spectral Centrality for Distributed Graphs via Homomorphic Encryption
Authors: Claire Guichemerre (Université de Rennes, CNRS, Irisa), Tristan Allard (Université de Rennes, CNRS, Irisa), Sofiane Azogagh (Université du Québec à Montréal), Marc-Olivier Killijian (Université du Québec à Montréal), Sébastien Gambs (Université du Québec à Montréal), Amr El Abbadi (University of California Santa Barbara)
Volume: 2026
Issue: 4
Pages: 869–890
DOI: https://doi.org/10.56553/popets-2026-0149
Artifact: Available, Functional, Reproduced
Abstract: In this paper, we introduce POPPY, a novel suite of privacy-preserving algorithms designed for computing spectral centrality measures over graphs distributed across mutually distrustful data centers. POPPY is the first approach that achieves together generality, accuracy, and scalability with respect to the number of participants. POPPY uses the CKKS fully homomorphic encryption scheme to support the arithmetic division operation over ciphertexts. POPPY consists of three variants: POPPYs, optimized for sparse graphs using SIMD operations; POPPYd, tailored for dense graphs through efficient encrypted matrix-vector multiplication; and POPPYh, a hybrid between POPPYs and POPPYd for coping with contexts involving a large number of remote nodes. In addition to its core algorithms, POPPY comes with a pruning strategy based on a new notion of node equivalence called INC-equivalence. Pruning is indeed of utmost importance when using fully homomorphic encryption in order to minimize the number of encrypted operations performed. The INC-equivalence notion allows us to eliminate redundant nodes efficiently and without any impact on the accuracy of the centrality scores. Our comprehensive theoretical analysis and empirical evaluation on real-world and synthetic datasets demonstrate that POPPY achieves together generality, accuracy, and scalability.
Keywords: Privacy-preserving data analytics, spectral centrality measure, distributed graph processing, fully homomorphic encryption
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
