  This paper studies the average consensus problem with differential privacy of
initial states, for which it is widely recognized that there is a trade-off
between the mean-square computation accuracy and privacy level. Considering the
trade-off gap between the average consensus algorithm and the centralized
averaging approach with differential privacy, we propose a distributed
shuffling mechanism based on the Paillier cryptosystem to generate correlated
zero-sum randomness. By randomizing each local privacy-sensitive initial state
with an i.i.d. Gaussian noise and the output of the mechanism using Gaussian
noises, it is shown that the resulting average consensus algorithm can
eliminate the gap in the sense that the accuracy-privacy trade-off of the
centralized averaging approach with differential privacy can be almost
recovered by appropriately designing the variances of the added noises. We also
extend such a design framework with Gaussian noises to the one using Laplace
noises, and show that the improved privacy-accuracy trade-off is preserved.
