Quantifying the Privacy of Exact Hiding Algorithms

The exact hiding algorithms that were presented in Chapters 14, 15, and 16 are all based on the principle of minimum harm (distortion), which requires the minimum amount of modifications to be made to the original database to facilitate sensitive knowledge hiding. As an effect, in most cases (depending on the problem instance at hand), the sensitive itemsets are expected to be positioned just below the revised borderline in the computed sanitized database

$$\mathcal{D}$$

. However, the selection of the minimum support threshold based on which the hiding is performed can lead to radically different solutions, some of which are bound to be superior to others in terms of offered privacy. In this chapter, we present a layered approach that was originally proposed in [27], which enables the owner of the data to quantify the privacy that is offered on a given database by the employed exact hiding algorithm. Assuming that an adversary has no knowledge regarding which of the infrequent itemsets in

$$\mathcal{D}$$

are the sensitive ones, this approach can compute the disclosure probability for the hidden sensitive itemsets, given the sanitized database

$$\mathcal{D}$$

and a minimum support or frequency threshold

msup/mfreq

.