<p>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 <a href="https://github.com/frankmcsherry/blog/blob/master/posts/2016-08-16.md" rel="nofollow noreferrer">in his blog</a>:</p>
<blockquote>
<p>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 &quot;buzz off&quot; if my record is present in the input (but is otherwise discriminating).</p>
</blockquote>

CC BY-SA 4.0
2022-01-15T00:09:09.853Z
2022-01-15T00:09:09.853Z
Clement C.
<p>This question relates to a supposed counterexample to the No Free Lunch theorem governing data privacy mechanisms, <a href="http://www.cse.psu.edu/%7Eduk17/papers/nflprivacy.pdf" rel="nofollow noreferrer">as stated by Kifer et al</a> (Section 2.1).</p>
<p>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.</p>
<p>&quot;Usefulness&quot; 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 <em>discriminant</em> close to one, where said discriminant <span class="math-container">$\omega$</span> is defined as follows.</p>
<blockquote>
<p>Given an integer <span class="math-container">$k&gt;1$</span>, a privacy-preserving query processor (i.e. randomised algorithm) <span class="math-container">$\mathcal{A}$</span>, and some constant <span class="math-container">$c$</span>, we say that the discriminant <span class="math-container">$\omega(k, \mathcal{A}) \ge c$</span> if there exist k possible database instances <span class="math-container">$D_1, \ldots, D_k$</span> and disjoint sets <span class="math-container">$S_1, \ldots, S_k$</span>, such that <span class="math-container">$P(\mathcal{A}(D_i) \in S_i) \ge c$</span> for <span class="math-container">$i = 1, \ldots, k$</span> (the randomness depends only on <span class="math-container">$\mathcal{A}$</span>).</p>
</blockquote>
<p>The No Free Lunch Theorem then states</p>
<blockquote>
<p>Let <span class="math-container">$q$</span> be a query with <span class="math-container">$k$</span> possible outcomes. Let <span class="math-container">$\mathcal{A}$</span> be a privacy-infusing query processor with discriminant <span class="math-container">$\omega(k, \mathcal{A}) &gt; 1 - \epsilon$</span>. Then there exists a probability distribution <span class="math-container">$\mathcal{P}$</span> over database instances <span class="math-container">$D$</span> such that <span class="math-container">$q(D)$</span> is uniform, but for which an attacker, given <span class="math-container">$\mathcal{A(d)}$</span>, can guess <span class="math-container">$q(D)$</span> with probability at least <span class="math-container">$1 - \epsilon$</span>.</p>
</blockquote>
<p>The proof given in the paper appears elegant:</p>
<blockquote>
<p>Choose database instances <span class="math-container">$D_1, \ldots, D_k$</span> such that <span class="math-container">$\forall i, q(D_i) = i$</span>. Choose sets <span class="math-container">$S_1, \ldots, S_k$</span> as in the definition of discriminants above, so that <span class="math-container">$\omega(k, \mathcal{A}) \ge min_i P(\mathcal{A}(D_i) \in S_i &gt; 1-\epsilon$</span>, with the probability depending only on the randomness in <span class="math-container">$\mathcal{A}$</span>. Let <span class="math-container">$\mathcal{P}$</span> be uniform over <span class="math-container">$D_1, \ldots, D_k$</span>. The attacker's strategy is to guess <span class="math-container">$q(D) = i$</span> if <span class="math-container">$\mathcal{A}(D) \in S_i$</span> and to guess randomly if <span class="math-container">$\mathcal{A}(D)$</span> is not in any of the <span class="math-container">$S_i$</span>.</p>
</blockquote>
<p>While the theorem is widely cited, the choice of <span class="math-container">$S_i$</span> in the proof above appears dubious to: it seems not necessarily possible to make a choice such that <span class="math-container">$\omega(k, \mathcal{A}) \ge min_i P(\mathcal{A}(D_i) \in S_i &gt; 1-\epsilon$</span> for a <span class="math-container">$D_i$</span> from the first step.</p>
<p>Consider the following counterexample.</p>
<ul>
<li><span class="math-container">$D$</span> drawn from <span class="math-container">$\{1, 2, 3\}$</span></li>
<li><span class="math-container">$q(d) = \mathrm{true}$</span> if <span class="math-container">$d = 3$</span> else <span class="math-container">$\mathrm{false}$</span></li>
<li><span class="math-container">$\mathcal{A}$</span> maps <span class="math-container">$D$</span> to either <span class="math-container">$a$</span> or <span class="math-container">$b$</span> as follows
<ul>
<li><span class="math-container">$\mathcal{A}(1) = a$</span> with probability <span class="math-container">$1-\epsilon$</span> (else <span class="math-container">$b$</span>)</li>
<li><span class="math-container">$\mathcal{A}(2) = b$</span> with probability <span class="math-container">$1-\epsilon$</span> (else <span class="math-container">$a$</span>)</li>
<li><span class="math-container">$\mathcal{A}(3) = a$</span> with probability 0.5 (else <span class="math-container">$b$</span>)</li>
<li>Hence <span class="math-container">$\omega(k = 2, \mathcal{A}) = 1-\epsilon$</span>, since it is possible to almost perfectly discriminate input values 1 and 2.</li>
</ul>
</li>
</ul>
<p>It does not appear possible to instantiate <span class="math-container">$S_i$</span> and <span class="math-container">$D_i$</span> such that the construction in the proof holds, nor does it seem possible to learn anything about <span class="math-container">$q(D)$</span> with confidence <span class="math-container">$1-\epsilon$</span>.</p>
<p>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?</p>

CC BY-SA 4.0
2022-01-14T19:02:14.713Z
This might address your question. It seems Frank McSherry had similar concerns about the proof:
https://github.com/frankmcsherry/blog/blob/master/posts/2016-08-16.md
Thomas Steinke
<pr.probability><privacy>
Proof and interpretation of the No Free Lunch theorem in data privacy
Jnov
# Proof and interpretation of the No Free Lunch theorem in data privacy

(Asked by: username_0 on 2022-01-11)

This question relates to a supposed counterexample to the No Free Lunch theorem governing data privacy mechanisms, [as stated by Kifer et al](http://www.cse.psu.edu/%7Eduk17/papers/nflprivacy.pdf) (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?

**Tags:** pr.probability, privacy

> **Comments:**
> **username_1**: This might address your question. It seems Frank McSherry had similar concerns about the proof: https://github.com/frankmcsherry/blog/blob/master/posts/2016-08-16.md  

---

## 1 answers

### Answer by username_2 on 2022-01-15. Score: 3

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](https://github.com/frankmcsherry/blog/blob/master/posts/2016-08-16.md):

> 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).


---

