# Algorithmic Matching Attacks on Optimally Suppressed Tabular Data
## 3 Matching Attack
### Enumerating Candidate Tables  
We enumerate candidate tables by obtaining solutions of indefinite equations (1) and (2) involving cell variables of suppressed cells in the original table. We assume that cell variables for non-suppressed cells are replaced with the actual cell values as we do in Example 1 in Section 2.3. We denote the linear equations in (1) and (2) in a matrix form as follows.  
\[Ax=b \tag{32}\]  
where \(A\) is the coefficient matrix, \(x\) is a column vector of cell variables, and \(b\) is a column vector of marginal sums either on a row or a column. We here assume that we order cell variables in a table in a sequential order either by row or column.  
Let \(N(A)\) be the null space of matrix A such that  
\[N(A)=\{y\in\mathcal{Z}^{n}\mid Ay=0\} \tag{33}\]  
where \(n\) is the number of cell variables and \(\mathcal{Z}\) is the set of integers. If \(x_{1},x_{2}\in\mathcal{Z}^{n}\) are solutions to \(Ax=b\), that is \(Ax_{1}=b\) and \(Ax_{2}=b\), then \(A(x_{1}-x_{2})=0\). Thus, the difference between any two solutions belongs to the null space \(N(A)\). Therefore, any solution to the equation \(Ax=b\) can be expressed as the sum of a fixed solution \(v\) and some element in \(N(A)\); that is, the set \(S\) of all solutions to \(Ax=b\) is defined as follows.  
\[S=\{v+y\mid Av=b\wedge y\in N(A)\}. \tag{34}\]  
Since the null space is represented by the linear combinations of independent vectors, we can enumerate all possible solutions that satisfy the non-negative constraints in (3) systematically.  
**Example 2**.: _Suppose that we have a suppressed table in Table 1. There are four suppressed cells whose cell variables are \(v_{1}\), \(v_{2}\), \(v_{3}\), and \(v_{4}\), respectively._  
_Then, the linear equations of the form \(Ax=b\) in (32) are represented as_  
\[\begin{bmatrix}1&1&0&0\\ 0&0&1&1\\ 1&0&1&0\\ 0&1&0&1\end{bmatrix}\begin{bmatrix}x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\end{bmatrix}=\begin{bmatrix}23\\ 9\\ 23\\ 9\end{bmatrix}. \tag{35}\]  
\begin{table}
\begin{tabular}{c c c c c c} \hline  & \(\mathbf{P_{1}}\) & \(\mathbf{P_{2}}\) & \(\mathbf{P_{3}}\) & \(\mathbf{P_{4}}\) & **Sum** \\ \hline \(M_{1}\) & 15 & 15 & 12 & 10 & 52 \\ \(M_{2}\) & 19 & \(x_{1}\) & 13 & \(x_{2}\) & 55 \\ \(M_{3}\) & 8 & 8 & 11 & 14 & 41 \\ \(M_{4}\) & 9 & \(x_{3}\) & 26 & \(x_{4}\) & 44 \\ \hline Sum & 51 & 46 & 62 & 33 & 192 \\ \hline \end{tabular}
\end{table}
Table 1: An example of a suppressed table. Each suppressed cell \(i\) is represented by a cell variable \(v_{i}\).  
_A vector \(v=[14,9,9,0]^{T}\) is a solution to Equation (35) and the null space \(N(A)\) is represented as_  
\[N(A)=\left\{k\left[1\quad-1\quad-1\quad 1\right]^{T}\big{|}\quad k\in\mathcal{Z}\right\} \tag{36}\]  
_Since each variable takes a non-negative value, we represent the set \(S\) of all possible combinations of cell values as_  
\[S=\left\{\left[14\quad 9\quad 9\quad 0\right]^{T}+k\left[1\quad-1\quad-1 \quad 1\right]^{T}\big{|}\quad k\in\mathcal{Z}\quad\wedge\quad 0\leq k\leq 9\right\} \tag{37}\]  
In this example, the dimension of the null space is 1, but, in general, the null space is represented as a linear combination of multiple column vectors.