# Algorithmic Matching Attacks on Optimally Suppressed Tabular Data
## 2 Background
### Safety of Suppressed Tabular Data  
To determine whether a given choice of secondary suppressed cells properly protects the values of primary suppressed cells, we need to verify that each primary suppressed cell has enough uncertainty on its value under the presence of linear relations concerning marginal sums. We consider a two-dimensional table \(T\) of \(r\) rows by \(c\) columns without loss of generality. Figure 3 shows linear  
Figure 2: Two-step procedure for protecting sensitive cells in a frequency table. We consider the cell \((M_{1},P_{1})\) sensitive because its value—7—is smaller than the minimum frequency threshold—10. We represent primary and secondary suppressed cells by symbols \(-\) and \(*\) respectively. relations in table \(T\). We denote by \(a_{ij}\) the value of cell \((i,j)\) in \(T\) and express the linear relations on marginal sums as follows:  
\[\sum_{j=1}^{c}a_{ij} =a_{i(c+1)} \text{for every row $i$, and} \tag{1}\] \[\sum_{i=1}^{r}a_{ij} =a_{(r+1)c} \text{for every column $j$.} \tag{2}\]  
We also assume that every cell takes a non-negative value as in the case of a frequency table, that is,  
\[a_{ij}\geq 0\quad\text{for every cell $(i,j)$} \tag{3}\]  
Suppose that we suppress some cells in \(T\) and obtain a suppressed table \(T^{\prime}\). To quantify the uncertainty of suppressed cell values in \(T^{\prime}\), we introduce a cell variable \(x_{ij}\) for each cell \((i,j)\) of \(T^{\prime}\). We also introduce the notion of a suppression pattern \(y\), which is a binary matrix of the same size as table \(T^{\prime}\). The suppression pattern \(y\) specifies which cells in table \(T^{\prime}\) are suppressed such that:  
\[y_{ij}= \begin{cases}1&\text{if cell $(i,j)$ in label $T^{\prime}$ is suppressed}\\ 0&\text{otherwise}\end{cases}  \tag{4}\]  
We can obtain the lower bound \(\underline{x_{ij}}\) of each primary suppressed cell \((i,j)\) by solving the ILP problem below. minimize \[x_{ij}\] (5) subject to \[\sum_{j=1}^{c}x_{ij} =x_{i(c+1)}\quad\text{for every row $i$}\] (6) \[\sum_{i=1}^{r}x_{ij} =x_{(r+1)c}\quad\text{for every column $j$}\] (7) \[x_{ij} =a_{ij}\quad\text{if}\quad\text{for every cell $(i,j)$ with $y_{ij}=1$}\] (8) \[x_{ij} \geq 0\quad\text{for every cell $(i,j)$}\] (9)  
Equation (8) sets the value for \(x_{ij}\) to be the actual cell value \(a_{ij}\) if that cell is suppressed in \(T^{\prime}\), which is indicated by the value \(y_{ij}\) in suppression pattern \(y\). Similarly, we can obtain the upper bound \(\overline{x_{ij}}\) of cell \((i,j)\) by computing the maximum value of \(x_{ij}\) under the same constraints (6)-(9) of the above ILP problem. We now define the feasibility interval of a suppressed cell in table \(T^{\prime}\) as follows. Figure 3: Linear relationships among cell values concerning marginal sums. We denote the value of a cell \((i,j)\) by \(a_{ij}\). Since there are \(r\) rows and \(c\) columns in the table, there are \(r+c\) linear equations. **Definition 2** (Feasibility interval). : _Given a suppressed table \(T^{\prime}\) with a suppression pattern \(y\), the feasibility interval for a suppressed cell \((i,j)\) is an interval \([x_{ij},\overline{x_{ij}}]\) between the lower and upper bounds of cell variable \(x_{ij}\) and its width is defined as the delta between the two end points; that is,_  
\[w_{ij}=\overline{x_{ij}}-\underline{x_{ij}}. \tag{10}\]  
We quantify the uncertainty of a primary suppressed cell with the width of its feasibility interval and require that the width of the feasibility interval of every primary suppressed cell is greater than a given threshold value \(\delta\) for the minimum width, as shown in Figure 4.  
We consider that a suppressed table \(T^{\prime}\) is safe if every primary suppressed cell in \(T^{\prime}\) is safe. **Definition 3** (Safety of a suppressed table \(T^{\prime}\)).