Privacy-preserving Average Consensus: Privacy Analysis and Optimal Algorithm Design
For distributed consensus systems, this work provides a formal privacy quantification and an optimal algorithm, though it is incremental as it builds on existing noise-adding methods.
This paper introduces a new privacy definition (ε, δ)-data-privacy to quantify the degree of privacy protection in average consensus, proves that the general privacy-preserving average consensus (GPAC) achieves this privacy with closed-form expressions, and shows that uniform noise is optimal. An optimal algorithm (OPAC) is proposed to achieve the highest privacy and avoid compromission.
Privacy-preserving average consensus aims to guarantee the privacy of initial states and asymptotic consensus on the exact average of the initial value. In existing work, it is achieved by adding and subtracting variance decaying and zero-sum random noises to the consensus process. However, there is lack of theoretical analysis to quantify the degree of the privacy protection. In this paper, we introduce the maximum disclosure probability that the other nodes can infer one node's initial state within a given small interval to quantify the privacy. We develop a novel privacy definition, named $(ε, δ)$-data-privacy, to depict the relationship between maximum disclosure probability and estimation accuracy. Then, we prove that the general privacy-preserving average consensus (GPAC) provides $(ε, δ)$-data-privacy, and provide the closed-form expression of the relationship between $ε$ and $δ$. Meanwhile, it is shown that the added noise with uniform distribution is optimal in terms of achieving the highest $(ε, δ)$-data-privacy. We also prove that when all information used in the consensus process is available, the privacy will be compromised. Finally, an optimal privacy-preserving average consensus (OPAC) algorithm is proposed to achieve the highest $(ε, δ)$-data-privacy and avoid the privacy compromission. Simulations are conducted to verify the results.