Observability Blocking for Functional Privacy of Dynamic Networks

This paper addresses the problem of identifying the minimum set of state variables in a network that must be protected from direct measurements by existing sensors to ensure functional privacy. Central to our work is the novel insight that functional observability is inherently linked to the ability of inferring a linear functional of states, which underpins the concept of functional privacy. Our goal is to prevent curious observers or eavesdroppers from deducing a linear functional of the states, either vector-wise or entry-wise. We prove that both problems are NP-hard. However, by assuming a reasonable diagonalizability condition and a constant bound on the geometric multiplicities of the system's eigenvalues, we present a polynomial-time complexity exact algorithm for the vector-wise functional privacy protection problem. Building on this algorithm, we propose a greedy algorithm for addressing the entry-wise privacy protection problem. Furthermore, we extend our results to structured systems where only the zero-nonzero patterns of system matrices, rather than their exact parameter values, are known. Our approach leverages a relationship between these problems and (structural) functional observability, utilizing a PBH-like criterion for assessing (structural) functional observability. Finally, two examples are provided to illustrate the effectiveness of our proposed approaches.