Matching Attacks on Non-deterministic Algorithms for Cell Suppression Problem for Tabular Data

The objective of the cell suppression problem (CSP) is to protect sensitive cell values in tabular data under the presence of linear relations concerning marginal sums. Previous algorithms for solving CSPs ensure that every sensitive cell has enough uncertainty on its values based on the interval width of all possible values. However, every deterministic CSP algorithm is vulnerable to an attack scheme that narrows down the width of sensitive cell values by matching the suppression pattern of an original table with that of each candidate table with the same CSP algorithm. Although to make a CSP algorithm non-deterministic is a promising approach against the matching attack, we find that there still exists an expanded matching attack to the algorithm.