Consider a hospital dataset with 100,000 patients, where only one has a rare genetic disease. To protect privacy, the hospital enforces 50,000-anonymity: it only answers aggregate queries covering at least half of the records. But can the record of the patient with the rare disease still be isolated? And if so, how many queries would it take? In this post, I show that, perhaps surprisingly, as few as 20 queries - each covering on average 50,000 patients - can be enough to isolate the single patient with the rare genetic disease.

A similar situation arises when aggregating the decisions or contributions of multiple agents or experts across several rounds to improve robustness and protect privacy, for example, by mitigating hallucinations, correcting erroneous (or even malicious) individual decisions, or aggregating model parameters in collaborative (federated) learning to avoid directly sharing sensitive training data. To guarantee confidentiality for participants, cryptographic primitives such as secure aggregation ensures that one can only access aggregate statistics over a random subset of at least $k$ participants in each round, but never the individual contributions. But is this level of protection sufficient? And if not, how many rounds (or queries) would be enough to reveal the private contributions of all participants?

The Problem

We assume that all queries are counting queries represented by a binary query matrix $A$, where $A_{i,j}=1$ if query $i$ covers record $j$, and $A_{i,j}=0$ otherwise. For example, the SQL query

SELECT COUNT(*) FROM Patients WHERE AGE = 32 and SEX = 'F'

counts the number of HIV+ patients who are both 32 years old and female. In terms of the matrix $A$, such a query corresponds to a row selecting exactly those records that satisfy the predicate after the WHERE clause.

Suppose we have $n$ patients and $m$ counting queries. Let $x_j$ be a Boolean value indicating whether patient $j$ is HIV-positive. Then, for query $i$, the result is

where $b_i$ is the number of HIV-positive patients covered by query $i$.

We consider an adversary who (1) aims to design the query structure $A$ (i.e., which patients are covered by which queries), and (2) knows the query results $b$. The adversary’s goal is to reconstruct the unknown vector $x$. Importantly, the database manager only answers a query $A_i$ if it covers at least $k$ patients, ensuring a minimal privacy guarantee with $k$-anonymity.

The key questions we explore in this post are:

1. How an adversary should choose the queries, and hence design $A$, so that $x$ can be reconstructed from $b$?
2. How many queries are required for such an attack?

The fewer queries needed, the cheaper the attack becomes, and the harder it is to detect.

The Theory

In the previous post, I showed how individual records can be reconstructed from the results of aggregated SUM queries by solving a system of equations of the form $A\cdot x=b$, where $A$ is the query matrix, $x$ is the vector of unknowns, and $b$ contains the query results. In that setting, any unknown $x_i$ can be recovered if its corresponding column $A_{:,i}$ is linearly independent of all other columns of $A$.

Let us look for a matrix $A$ whose columns are linearly independent, assuming for simplicity that $m=n$. Rather than verifying linear independence directly, it is often easier to check orthogonality, which is a stronger condition and automatically implies linear independence.

Because $A$ is restricted to be binary (each query either includes $x_i$ or not), there is in fact only a single $n\times n$ binary matrix with orthogonal columns: the standard basis (aka identity matrix), in which each column is a unit (one-hot) vector. For example, for four records (and queries) the standard basis is:

The problem with using the standard basis $\mathbf{I}$ is that each query covers only a single record. This corresponds to a trivial disclosure with zero anonymity and would never be answered by a database manager providing $k$-anonymity for any $k>1$. We are interested in the more realistic case where every query covers multiple records, that is, $A$ is a binary matrix in which each row contains multiple ones. However, based on the argument above, no such square binary matrix with orthogonal columns exists.

However, the situation changes if we allow negative entries in the query matrix, that is, we can not only add but also subtract attribute values from the aggregates. Consider the Hadamard matrix, where the first row and column are constant $1$, and every other row and column contains an equal number of $+1$ and $-1$. For example, the Hadamard matrix of size 4 is

In general, a Hadamard matrix of size $n$ can be constructed recursively as

with $H_1=[1]$. Because Hadamard matrices are orthogonal by construction, every pair of columns (and rows) is linearly independent.

Although the Hadamard matrix is not strictly binary (entries are $\pm 1$ rather than $0/1$), its rows are the linear combination of strictly binary queries; the sum of the records with negative entries in a row can be expressed as the total sum of all records minus the sum of the records with positive entries. More precisely, define a binary matrix $H^{\prime }$ by replacing each $-1$ in $H$ with $0$:

Then, for any row $i$,

where $H_{1,:}^{\prime }=H_{1,:}$ is the vector of all-ones, hence $\sum _i{x}_i=⟨H_{1,:}^{\prime },x⟩$. This means the adversary can request the database to evaluate all binary queries in $H^{\prime }$, obtaining $b^{\prime }=H^{\prime }x$. From these query results, the adversary can reconstruct the original Hadamard query responses $b=Hx$, and then solve the resulting system of equations to recover $x$. The Hadamard matrix is particularly appealing since each query (row) covers half of the records (so it appears "highly aggregated" and compliant with $k$-anonymity type privacy rules), and the resulting system can be inverted efficiently using the fast Walsh–Hadamard transform in $\mathcal{O}(n\log n)$ time.

In conclusion, the adversary can recover every record using a number of queries equal to the total number of records, even though each query aggregates over half of the database.

Can the adversary reconstruct all $n$ records with less than $n$ queries?

If we have more unknowns (records) than equations (queries), the above system of linear equations $Ax=b$ is underdetermined and cannot be solved in general. However, it is no longer the case if $x$ is sparse, that is, it has less than $m$ non-zero elements like in the hospital dataset above where we have only a single HIV-positive patient. Indeed, we only need to determine the non-zero elements in $x$ whose number is significantly smaller than $n$. Vectors with $s$ nonzero entries are also called $s$-sparse vectors, and the set of non-zero positions is called the support of this vector.

Our objective is to minimize the number of queries $m$, given that the dataset is $s$-sparse, i.e., it contains only $s\ll n$ nonzero entries. Equivalently, we seek a query matrix $\mathbf{A}$ with as few rows as possible. Trivially, $m\le n$, as shown above. On the other hand, $m\ge s$, since $\mathbf{A}x$ is a linear combination of the columns of $\mathbf{A}$. If we knew which $s$ coordinates were nonzero, we could simply query those coordinates with $s$ linearly independent rows, which would be sufficient for recovery (because the number of linearly independent rows equals the number of independent columns). Thus, in principle, the answers to $\mathcal{O}(s)$ queries contain enough information.

However, the indices of the nonzero entries is unknown. A classical result in linear algebra states that if every subset of $2s$ columns of $\mathbf{A}$ is linearly independent, then the sparsest solution to $\mathbf{A}x=b$ is unique for any $s$-sparse vector $x$. Consequently, $2s$ linear (not necessarily binary) queries are sufficient to guarantee unique recovery of any $s$-sparse vector.

This proof suggests a simple brute-force search to recover $x$: enumerate all possible $s$-sparse candidates $x$ and select the one that satisfies $\mathbf{A}x=b$, which must be the single correct solution. Unfortunately, this requires solving $(\genfrac{}{}{0ex}{}{n}{s})$ linear systems, which quickly becomes infeasible as $s$ grows. In fact, it can be shown that finding the sparsest solution (i.e., solving the ${\ell }_0$-minimization problem) is NP-complete for arbitrary choices of $\mathbf{A}$ and $x$ (unless $\mathrm{P}=\mathrm{NP}$). Fortunately, for specially designed matrices $\mathbf{A}$, there exist efficient algorithms that can recover $s$-sparse signals. These will be discussed next.

We're looking for a $m\times n$ rectangular matrix such that every set of $2s$ columns of this matrix is linearly independent. More formally, the question: is there a rectangular $(m\times n)$ matrix whose any $(m\times m)$-sized submatrix is invertible? One construction is the Vandermonde matrix:

if $c_0,\dots ,c_{m-1}$ are all positive and distinct.

Error correcting codes for reconstruction

We require a binary query matrix $A$, where an attribute $x_j$ is either included in the aggregate ($A_{i,j}=1$) or excluded ($A_{i,j}=0$) for a given query. As shown above, there is no such square matrix that allows reconstruction of $x$, except for the trivial and non-private choice of the standard basis. However, this limitation no longer holds if we consider finite field arithmetic, which connects the problem to binary error-correcting codes.

In particular, a practical instantiation of a Vandermonde matrix is the parity-check matrix of a binary BCH code:

where $\{{\alpha }_0,\dots ,{\alpha }_{m-1}\}$ are distinct elements of a finite field of size at least $n$. In practice, the field is typically $GF(2^q)$, while the code symbols are restricted to $GF(2)$, yielding binary codewords. The code length is then $n=2^q-1$, and if $m=2s$, the BCH code can correct up to $s$ errors in a codeword as long as all ${\alpha }_i$ are distinct field elements. Therefore, if $x$ is interpreted as a potentially corrupted codeword of this BCH code, then the nonzero locations of $x$ can be identified from its syndrome $H\cdot x$ using any efficient BCH decoding procedure. This is because the zero vector is always a valid codeword of linear code, and all vectors with at most $2s$ nonzero entries will decode to the zero vector. Put simply, once $H\cdot x$ can be computed, the adversary can in principle solve for $x$ in $GF(2^q)$.

The problem that $H$ is not binary, its entries live in $GF(2^q)$. Therefore, the inner products $⟨H_i,x⟩$ must be computed over $GF(2^q)$, requiring finite-field arithmetic, which is seemingly not realizable in SQL. However, one can expand each field element of $GF(2^q)$ into a binary vector of length $q$ (via a basis representation of the field). With this expansion, the parity-check matrix can be represented as a binary matrix which means that a single query $⟨H_i,x⟩$ can be realized with exactly $q=\log (n)$ binary queries.

Therefore, the adversary can transform $H$ into a binary matrix $A$ with $m\cdot q=m\cdot {\log }_2(n+1)$ rows. By querying the database to compute $A\cdot x$ instead of $H\cdot x$ using standard integer arithmetic, and then reducing the result elementwise modulo 2, the adversary obtains the binary representation of the syndrome $H\cdot x$ in $GF(2)$ which then can be directly mapped to its original representation in $GF(2^q)$. Finally, standard BCH decoding can be applied on $H\cdot x$ in $GF(2^q)$ to efficiently reconstruct $x$. In total, this reconstruction procedure requires $2s\cdot {\log }_2(n+1)=\mathcal{O}(s{\log }_{2}n)$ binary queries.

How many records are covered by a binary query $A_i$? It is not hard to see that if ${\alpha }_i$ used in the parity check matrix $H$ is a primitive element of $GF(2^q)$, then every query $A_i$ covers about half of the records.

In conclusion, an adversary can exactly reconstruct all records in a database containing $s$ nonzero entries using only $2s\log n$ binary queries, even though each individual query covers roughly half of the records, that is, they are $n/2$-anonym.

Stable reconstruction

The reconstruction techniques described above work only under strong assumptions: namely, that the sparsity $s$ of $x$ is known in advance, that the database manager returns exact query results (i.e., without perturbations as in Differential Privacy), and that the adversary has fairly accurate knowledge of patients' non-sensitive attributes (those appearing in the WHERE clause of SQL queries) in order to select the exact records targeted by the pre-defined queries. If these conditions are not satisfied, the recovered vector may significantly differ from the true $x$, rendering these techniques unstable. This concern is realistic; for example, an adversary may not know the exact number of AIDS patients, especially if the number is small, and querying it directly would violate $k$-anonymity.

Moreover, the binary code construction described earlier is not even asymptotically optimal in terms of the number of binary queries required. While a naive argument suggests that identifying a single non-zero position among $n$ requires ${\log }_2(n)$ bits and thus at least $s{\log }_2(n)$ binary queries in total, support recovery does not require distinguishing every position individually. Instead, to uniquely identify all subsets of size s, one needs

binary queries.

This raises a natural question: is there a stable reconstruction technique that does not rely on rigidly pre-defined query structures? The answer comes from compressed sensing, which provides methods that are not only stable but also asymptotically optimal. Using a carefully designed random query matrix, the support of an $s$-sparse vector can be reconstructed with only $\mathcal{O}(s\ln (n/k))$ queries, while tolerating noise and perturbations in the responses. As a plus, the same techniques also work for non-binary queries!

We want a matrix $A$ such that every submatrix $A_S$ (formed by selecting $m$ columns of $A$) is close to orthogonal. Orthogonality guarantees that the columns are linearly independent, meaning the dot product between any pair of columns (rows) is zero, or equivalently, $A_S^{\mathrm{\top }}{A}_S=A_S{A}_S^{\mathrm{\top }}=\mathbf{I}$. In practice, exact orthogonality is often too strong to require, so we instead demand that $A_S^{\mathrm{\top }}{A}_S$ be close to the identity matrix, or in other words, $(A_S^T\cdot A_S-\mathbf{I})$ is small according to a suitable norm, such as the matrix (or operator) norm. Formally, this means that $\underset{\parallel u{\parallel }_2\le 1}{max}\parallel (A_S^{\mathrm{\top }}{A}_S-\mathbf{I})u{\parallel }_2=\delta$ is as small as possible. Intuitively, this condition says that $A_S^{\mathrm{\top }}{A}_S-\mathbf{I}$ squeezes any unit vector to almost zero. Equivalently, since $A_S^{\mathrm{\top }}{A}_S-\mathbf{I}$ is symmetric, we have for any vector $x$:

But the left-hand side equals

so we obtain:

and hence:

Thus, when $\delta$ is small, the “stretching” or “shrinking” effect of the transformation $A_S$ is negligible: $A_S$ acts almost like an isometry that preserves ${\ell }_2$-norms (and hence distances between vectors). Orthogonal matrices achieve this exactly, since they preserve the inner product: $⟨A_{S}x,A_{S}y⟩=x^{\mathrm{\top }}(A_S^{\mathrm{\top }}{A}_S)y=x^{\mathrm{\top }}y=⟨x,y⟩$ and therefore the ${\ell }_2$-norm: $||x|{|}_2=⟨x,x{⟩}^{1/2}=⟨A_{S}x,A_{S}x{⟩}^{1/2}=||A_{S}x|{|}_2$. The constant $\delta$ measures how far $A_S$ deviates from perfect orthogonality; if the same $\delta$ works for all submatrices $A_S$ of $A$, it is called the restricted isometry constant of $A$.

Random query matrix

Let $A_{i,j}$ be $1$ or $-1$ with equal probability for every $i,j$ independently. Then, for any row $A_i$,

due to independence (i.e., $E[A_{i,\ell }{A}_{i,k}]=1$ for $k=\ell$ and 0 otherwise) and $E\left[A_{i,j}^2\right]=1^2\cdot 0.5+(-1{)}^2\cdot 0.5=1$ is the variance. For the whole matrix $A$:

which means that, on expectation, the matrix $\frac{1}{\sqrt{m}}A$ will preserve the norm and has a good chance to be "quasi-orthogonal". However, to have a better estimate on how close we are to perfect orthogonality, we need to know how well $E(\frac{1}{m}\parallel Ax{\parallel }_2^2)$ concentrates around its mean $||x|{|}_2^2$, that is, what's the probability that $\frac{1}{m}\parallel Ax{\parallel }_2^2-\parallel x{\parallel }_2^2$ is outside of a certain range of 0.

We will derive a more general result for a wider family of random matrices that will reveal a few design principles about the queries. We will show that if the elements of the matrix $\mathbf{A}$ “tightly” concentrate around their mean 0, then the same holds for the inner products $⟨A_i,x⟩$. Consequently, the squared quantities $⟨A_i,x{⟩}^2$ also “tightly” concentrate around their mean value $\parallel x{\parallel }_2^2$, and therefore the average $\frac{1}{m}\parallel \mathbf{A}x{\parallel }_2^2$ does as well. More precisely, if the entries of $A$ are subgaussian, then it follows that both the random variables $⟨A_i,x{⟩}^2$ and $\frac{1}{m}\parallel \mathbf{A}x{\parallel }_2^2$ are subexponential in $m$. Intuitively, this means that the probability that $\mathbf{A}$ deviates from perfect orthogonality is exponentially small in the number of rows $m$. Thus, the larger the number of rows, the more “orthogonal” the columns of $\mathbf{A}$ become, on average.

But why do we want subexponential concentration? Because we want "approximate orthogonality" to hold not just for a single submatrix of $A$, but any submatrices of a given size $s$ simultaneously. Indeed, if $\frac{1}{m}\parallel {\mathbf{A}}_{S}x{\parallel }_2^2$ is subexponential then roughly

Applying a union bound over all possible subsets $S$ of size $s$, we obtain

We want this overall failure probability to be much smaller than 1. Therefore, we require
$(\genfrac{}{}{0ex}{}{n}{s})\beta e^{-\kappa m}\ll 1$. Taking logarithms on both sides gives the condition:

Using the standard combinatorial upper bound $(\genfrac{}{}{0ex}{}{n}{s})\le (en/s{)}^s$ and ignoring constants $\kappa$ and $\beta$, we find that

In other words, subexponential concentration is useful because it gives you exponentially small failure probabilities for each event, which allows us to extend guarantees that hold for a single submatrix to exponentially many submatrices simultaneously, without requiring exponentially many queries (rows).

Next, we will provide more mathematical details on how to prove subexponential (or subgaussian) concentration using one of the most versatile tools in the theory of randomized algorithms: the Chernoff bound. In particular, we will show the following chain of implications for a single submatrix $A_S$:

Any entry of $A_S$ is subgaussian $\stackrel{\text{Step 1}}{⟹}$ $⟨A_i,x⟩$ is subgaussian $\stackrel{\text{Step 2}}{⟹}$ $⟨A_i,x{⟩}^2$ is subexponential $\stackrel{\text{Step 3}}{⟹}$ $\frac{1}{m}\parallel A_{S}x{\parallel }_2^2$ is subexponential $⟹$ $A_S$ is "quasi-orthogonal"

Finally, we extend this subexponential concentration for all submatrices of $A$.

Concentration of a single submatrix

To decide if a random variable $X$ is subgaussian (or subexponential), one need to check the moment generating function (MGF) $\mathbb{E}[e^{\lambda X}]$ of $X$, which is intimately related to the tail bound based on Chernoff bounds:

One direct implication of Chernoff bound that if $\mathbb{E}[e^{\lambda X}]\le \exp \left(c{\lambda }^2\right)$ for a constant $c$, then $X$ is subgaussian: $Pr(|X|\ge t)\le 2\cdot e^{-\frac{t^2}{4c}}$

In fact, for any centered subgaussian random variable $X$, $\mathbb{E}[e^{\lambda X}]\le e^{c{\lambda }^2/2}$ implies that $E[X^2]\le c$ that is also called the proxy variance of $X$.

From now on, we’ll assume that $X=A_{i,j}$ is a subgaussian random variable: $\mathbb{E}[e^{\lambda X}]\le \exp \left(c{\lambda }^2/2\right)$ with proxy variance $E[X^2]\le c$.

For example, when $A_{i,j}=1$ or $A_{i,j}=-1$ with probability $0.5$, the moment generating function (MGF) of $X=A_{i,j}$ is

and therefore $Pr(|X|\ge t)\le 2\cdot e^{-\frac{t^2}{2}}$ (the same bound can also be derived from Hoeffding's inequality). The proxy variance $2\cdot (1/2)=1$ equals the true variance.

Step 1: $A_{i,j}$ is i.i.d subgaussian $⟹$ $⟨A_i,x⟩$ is subgaussian

One can show that if $A_{i,j}$ is subgaussian with proxy variance $c$, then $⟨A_i,x⟩$ is also subgaussian with proxy variance $c\parallel x{\parallel }_2^2$.

Step 2: $⟨A_i,x⟩$ is subgaussian $⟹$ $⟨A_i,x{⟩}^2$ subexponential

Recall that $\mathbb{E}[⟨A_i,x{⟩}^2]=\parallel x{\parallel }_2^2$. Let's assume (we'll relax this later) that $\mathbb{E}[⟨A_i,x{⟩}^2]=\parallel x{\parallel }_2^2\le 1$.
Then,