Censoring statistical tables to protect sensitive information: easy and hard problems

Protecting sensitive information in a two-dimensional table asked for by a statistical user of a database raises computational problems involving both the query system which should guarantee the data security, and the user who should be able to disclose sensitive data when it is unprotected. We provide a quadratic algorithm which allows the query system to test a censored table for security, and a linear algorithm to find a minimum number of suppressions sufficient for protecting all sensitive cells; however, if sensitive information refers not only to single cells but also to cell sets, we prove that the problem of minimizing the number of suppressions is NP-hard. Finally, we provide a cubic algorithm which allows a user to disclose sensitive information in a censored table