A Graph Theoretic Approach to Statistical Data Security
Dan Gusfield · SIAM Journal on Computing · 1988
In this paper we study the problem of protecting sensitive data in an n by n two-dimensional table of statistics, when the nonsensitive data are made public along with the row and column sums for the table. A sensitive cell is considered unprotected if its exact value can be deduced from the nonsensitive cell values and the row and column sums. We give an efficient algorithm to identify all unprotected cells in a table. The algorithm runs in linear time if the sensitive values are known, and in $O(n^3 )$ time if they are not known. We then consider the problem of suppressing the fewest additional cell values to protect all the sensitive cells, when some cells are initially unprotected. We give a linear time algorithm for this problem in the useful special case that all cell values are strictly positive. We next consider the problem of computing the tightest upper and lower bounds on the values of sensitive cells. We show that each cell bound can be computed in $O(n^3 )$ time, but all $\Theta (n^2 )$ values can be computed in $O(n^4 )$ total time. In the case that all the cells are sensitive, we show that trivial methods compute the tightest bounds, and in fact, the $n^2 $ lower bounds can be computed in $O(n)$ arithmetic and comparison operations. Although these problems at first appear to be problems in integer linear algebra, the solutions are based on computational graph theory, and the worst case times are significantly faster than for approaches based on linear algebraic computations.