How much noise suffices for privacy of multi-agent systems?

Abstract

As multi-agent systems always involve a large number of nodes and connections, it is crucial to study the privacy preserving problem with minimal “corrupted” noise in the framework of differential privacy or noise-perturbation schemes. We first show that a moderate amount of noise is sufficient to ensure privacy as long as the minimal observability subspace of the considered system is blurred by noise. Based on this, it is shown that blurring more than half of the sensors can provide a desirable level of privacy protection using a node-based privacy preserving mechanism. By formulating the problem of the minimal amount of noise injected into an optimization framework, we give conditions on the tradeoff between privacy preservation and the amount of the noise. To further reduce the amount of the injected noise, an edge-based privacy preserving mechanism is devised. It is found that less than half of the sensors blurred by noise still enable us to solve the privacy preserving problem if more constraints on the communication topology are imposed. Finally, some discussions and comparisons are conducted to demonstrate the effectiveness of our proposed privacy preserving strategies.