Protecting Sensitive Information in Cross-Tabulated Tables

Title: Protecting Sensitive Information in Cross-Tabulated Tables

Abstract: This research aims to investigate the complexity of protecting a broad class of information contained in two-dimensional tables that publish the values of all cells except a set of sensitive ones, which are suppressed. The study focuses on analytic invariants, which are power series in terms of the suppressed cells that have a unique feasible value and a convergence radius of infinity. The main research question is whether there exist nontrivial analytic invariants in terms of the suppressed cells, and the paper presents an optimal linear-time algorithm for testing this. Additionally, the paper discusses NP-completeness results and an almost linear-time algorithm for suppressing the minimum number of cells, adding to the sensitive ones, to prevent leaking analytic invariant information.

Methodology: The study uses mathematical analysis, mixed graph connectivity, and graph augmentation as methodological tools. It employs a two-dimensional table model with real or integer values, different bounds, and finite or infinite bounds. The upper bound of a cell should be strictly greater than its lower bound, and the bounds are necessary because some unsuppressed cells may later be suppressed.

Results: The research presents an optimal linear-time algorithm for testing whether there exist nontrivial analytic invariants in terms of the suppressed cells. It also discusses NP-completeness results and an almost linear-time algorithm for suppressing the minimum number of cells, adding to the sensitive ones, to prevent leaking analytic invariant information.

Implications: The findings of this research have practical implications for protecting sensitive information in cross-tabulated tables. By presenting an optimal algorithm for testing analytic invariants and discussing the suppression of cells, the study contributes to the development of more effective methods for safeguarding confidential data in such tables.

Link to Article: https://arxiv.org/abs/0101032v1 Authors: arXiv ID: 0101032v1