# Proof and interpretation of the No Free Lunch theorem in data privacy

This question relates to a supposed counterexample to the No Free Lunch theorem governing data privacy mechanisms, as stated by Kifer et al (Section 2.1).

Colloquially, the theorem states that no mechanism can guarantee both usefulness and data privacy in the absence of further assumptions on the statistical structure of the data to which it is applied.

"Usefulness" is a property of a data mechanism that is satisfied when said mechanism is able to provide an accurate answer to at least one query. Formally, useful mechanisms have a discriminant close to one, where said discriminant $$\omega$$ is defined as follows.

Given an integer $$k>1$$, a privacy-preserving query processor (i.e. randomised algorithm) $$\mathcal{A}$$, and some constant $$c$$, we say that the discriminant $$\omega(k, \mathcal{A}) \ge c$$ if there exist k possible database instances $$D_1, \ldots, D_k$$ and disjoint sets $$S_1, \ldots, S_k$$, such that $$P(\mathcal{A}(D_i) \in S_i) \ge c$$ for $$i = 1, \ldots, k$$ (the randomness depends only on $$\mathcal{A}$$).

The No Free Lunch Theorem then states

Let $$q$$ be a query with $$k$$ possible outcomes. Let $$\mathcal{A}$$ be a privacy-infusing query processor with discriminant $$\omega(k, \mathcal{A}) > 1 - \epsilon$$. Then there exists a probability distribution $$\mathcal{P}$$ over database instances $$D$$ such that $$q(D)$$ is uniform, but for which an attacker, given $$\mathcal{A(d)}$$, can guess $$q(D)$$ with probability at least $$1 - \epsilon$$.

The proof given in the paper appears elegant:

Choose database instances $$D_1, \ldots, D_k$$ such that $$\forall i, q(D_i) = i$$. Choose sets $$S_1, \ldots, S_k$$ as in the definition of discriminants above, so that $$\omega(k, \mathcal{A}) \ge min_i P(\mathcal{A}(D_i) \in S_i > 1-\epsilon$$, with the probability depending only on the randomness in $$\mathcal{A}$$. Let $$\mathcal{P}$$ be uniform over $$D_1, \ldots, D_k$$. The attacker's strategy is to guess $$q(D) = i$$ if $$\mathcal{A}(D) \in S_i$$ and to guess randomly if $$\mathcal{A}(D)$$ is not in any of the $$S_i$$.

While the theorem is widely cited, the choice of $$S_i$$ in the proof above appears dubious to: it seems not necessarily possible to make a choice such that $$\omega(k, \mathcal{A}) \ge min_i P(\mathcal{A}(D_i) \in S_i > 1-\epsilon$$ for a $$D_i$$ from the first step.

Consider the following counterexample.

• $$D$$ drawn from $$\{1, 2, 3\}$$
• $$q(d) = \mathrm{true}$$ if $$d = 3$$ else $$\mathrm{false}$$
• $$\mathcal{A}$$ maps $$D$$ to either $$a$$ or $$b$$ as follows
• $$\mathcal{A}(1) = a$$ with probability $$1-\epsilon$$ (else $$b$$)
• $$\mathcal{A}(2) = b$$ with probability $$1-\epsilon$$ (else $$a$$)
• $$\mathcal{A}(3) = a$$ with probability 0.5 (else $$b$$)
• Hence $$\omega(k = 2, \mathcal{A}) = 1-\epsilon$$, since it is possible to almost perfectly discriminate input values 1 and 2.

It does not appear possible to instantiate $$S_i$$ and $$D_i$$ such that the construction in the proof holds, nor does it seem possible to learn anything about $$q(D)$$ with confidence $$1-\epsilon$$.

Is the proof incorrect? If so, what exactly is the interpretation of the No Free Lunch Theorem? If not, how is the above counterexample misguided?

As mentioned by Thomas in a comment, indeed, there appears to be an issue with the definition (or the theorem; depending on how you look at it), specifically regarding the quantifiers. This is also discussed by Frank McSherry in his blog:

Unfortunately, the definition of discrimination doesn't require a computation to distinguish between any datasets, just some datasets. Maybe not these datasets. The proof doesn't hold, and indeed there are counter-examples to the theorem: consider a query which wants to read out my record, and a computation which says "buzz off" if my record is present in the input (but is otherwise discriminating).