Observability Blocking for Functional Privacy of Linear Dynamic Networks

This paper addresses the problem of determining the minimum set of state variables in a network that need to be blocked from direct measurements in order to protect functional privacy with respect to any output matrices. More precisely, the goal is to prevent adversarial observers or eavesdroppers from inferring a linear functional of states, either vector-wise or entry-wise. We relate the considered functional privacy to the concept of functional observability. Building on a PBH-like criterion for functional observability, we prove that both problems are NP-hard. However, by assuming a reasonable constant bound on the geometric multiplicities of the system's eigenvalues, we present an exact algorithm with polynomial time complexity for the vector-wise functional privacy protection problem. Based on this algorithm, we then provide a greedy algorithm for the entry-wise privacy protection problem. Finally, we provide an example to demonstrate the effectiveness of our proposed approach.