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?