Proof and interpretation of the No Free Lunch theorem in data privacy - Theoretical Computer Science Stack Exchange most recent 30 from cstheory.stackexchange.com 2022-01-26T17:49:08Z https://cstheory.stackexchange.com/feeds/question/50962 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cstheory.stackexchange.com/q/50962 3 Proof and interpretation of the No Free Lunch theorem in data privacy Jnov https://cstheory.stackexchange.com/users/65521 2022-01-11T17:14:21Z 2022-01-15T00:09:09Z <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> https://cstheory.stackexchange.com/questions/50962/-/50981#50981 3 Answer by Clement C. for Proof and interpretation of the No Free Lunch theorem in data privacy Clement C. https://cstheory.stackexchange.com/users/13319 2022-01-15T00:09:09Z 2022-01-15T00:09:09Z <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>