Abstract
Decentralised learning has recently gained traction as an alternative tofederated learning in which both data and coordination are distributed over itsusers. To preserve the confidentiality of users' data, decentralised learningrelies on differential privacy, multi-party computation, or a combinationthereof. However, running multiple privacy-preserving summations in sequencemay allow adversaries to perform reconstruction attacks. Unfortunately, currentreconstruction countermeasures either cannot trivially be adapted to thedistributed setting, or add excessive amounts of noise. In this work, we first show that passive honest-but-curious adversaries canreconstruct other users' private data after several privacy-preservingsummations. For example, in subgraphs with 18 users, we show that only threepassive honest-but-curious adversaries succeed at reconstructing private data11.0% of the time, requiring an average of 8.8 summations per adversary. Thesuccess rate is independent of the size of the full network. We consider weakadversaries, who do not control the graph topology and can exploit neither theworkings of the summation protocol nor the specifics of users' data. We develop a mathematical understanding of how reconstruction relates totopology and propose the first topology-based decentralised defence againstreconstruction attacks. Specifically, we show that reconstruction requires anumber of adversaries linear in the length of the network's shortest cycle.Consequently, reconstructing private data from privacy-preserving summations isimpossible in acyclic networks. Our work is a stepping stone for a formal theory of decentralisedreconstruction defences based on topology. Such a theory would generalise ourcountermeasure beyond summation, define confidentiality in terms of entropy,and describe the effects of (topology-aware) differential privacy.