Gossip Algorithms that Preserve Privacy for Distributed Computation Part II: Performance Against Eavesdroppers

Abstract

We propose gossip algorithms that preserve the sum of network values (and therefore the average), and in the meantime fully protect node privacy even against eavesdroppers possessing the entire information flow and network knowledge. We have shown in Part I of the paper that this type of privacy-preserving gossiping algorithms can be used as a simple encryption step in distributed optimization and computation algorithms. In this Part II, we investigate the underlying network dynamics of the proposed algorithms and present three categories of eavesdroppers. To show the Global Privacy Preservation property of the presented algorithms, we establish some concrete privacy-preservation performance analysis characterized by proving impossibilities for the reconstruction of the node initial values. Show more