A little knowledge goes a long way: faster detection of compromiseddata in 2-D tables

摘要

A reexamination is made of the problem of protecting sensitivedata in an n by n table of integer statistics, whenthe nonsensitive data are made public along with the row and column sumsfor the table. Consideration is given to the problem of computing thetightest upper bounds on the values of sensitive (undisclosed) cells.These bounds, together with tightest lower bounds (which can beefficiently computed), define precisely the smallest intervals that anadversary can deduce for the missing sensitive cell values. Smallintervals compromise the security of the undisclosed data, and in somecases violate laws on public data disclosure. It is observed that thenumber of initial needed bounds can be reduced fromO(n log n) to 2n-1 by exploiting arecent result of C.K. Cheung and T.C. Hu (1988)