What is the relation between differential-privacy mechanism and entropy?
Why do differential-privacy people care whether or not the noise function saturates the lower bound of Shannon entropy?
For example : Laplace distribution that is used to model the noise function happens to saturate the lower bound of Shannon entropy under epsilon differential privacy constraints. See Theorem 8 in Yu Wang, Zhenqi Huang, Sayan Mitra and Geir E. Dullerud, Entropy-minimizing Mechanism for Differential Privacy of Discrete-time Linear Feedback Systems for an example.
But what is the significance of this saturation?
complexity-theory cryptography information-theory
$\begingroup$ We expect you to do a significant amount of research and/or self-study before asking. What research/self-study have you done? What possible explanations have you considered? What are your thoughts? You seem to have concluded that differential-privacy people care whether or not (...) -- what's the basis for this conclusion? Please flesh out your question. Generally speaking, a one-sentence question is often a red flag indicating that you should take another look at your question to see if you've done as much research as you could have and provided enough context. $\endgroup$ – D.W.♦ Jun 22 '15 at 22:47
$\begingroup$ You've been given similar advice before: 1, 2, 3. I see you've already got quite a bit of experience on this site, but you might want to spend a little time at our help center, e.g., cs.stackexchange.com/help/how-to-ask, to refresh your knowledge of advice for how to ask good questions and use this site effectively. $\endgroup$ – D.W.♦ Jun 22 '15 at 22:51
$\begingroup$ I have added some more details. (I didn't give my specific details because I felt that this is a generic question and not tied to the examples I have seen) $\endgroup$ – user6818 Jun 23 '15 at 16:45
$\begingroup$ Thanks for the citation. That helps. However, I couldn't find a Lemma 8 in that paper. Do you mean Theorem 8? $\endgroup$ – D.W.♦ Jun 23 '15 at 17:57
$\begingroup$ FYI The link to the above paper is dead, but it can be found here: publish.illinois.edu/science-of-security-lablet/files/2014/06/… $\endgroup$ – Racing Tadpole May 15 '19 at 5:33
In general, if you're not sure about the significance of mathematical results in a published paper, often a good first place to look is the paper's introduction and/or conclusion. The authors often try to provide some explanation why you should care about their results in the introduction and conclusion.
In this case, the following two quotes from the introduction of the paper you cited provide a pretty clear explanation for why the authors care:
we first study an $\epsilon$-differentially private noise-adding mechanism for one-shot queries that provides the best output accuracy, which is measured by the Shannon entropy. [...]
In Section III, we prove that, for a one-shot $n$-dimensional input, there is a lower bound $n + n \ln(2\epsilon)$ on the entropy of the output for an $\epsilon$-differentially private noise-adding mechanism, and the lower bound is achieved by Laplacian noise with parameter $\epsilon$.
In other words, the Shannon entropy measures the accuracy of the output after adding the noise (lower is better); Theorem 8 proves that Laplace noise achieves the lowest possible Shannon entropy, in a particular situation; therefore, we can conclude that Laplace noise is optimal in the sense that it achieves the highest possible output accuracy, in that situation.
D.W.♦D.W.
$\begingroup$ I saw that but I would like to know from where does this come from : "Shannon entropy measures the accuracy of the output after adding the noise " ? The whole point of the noise is to create an obfuscation then why would you want it to be more accurate? $\endgroup$ – user6818 Jun 23 '15 at 19:21
$\begingroup$ @user6818, that's a different question, and should be asked separately. I think you need to start by reading about differential privacy and understand what the purpose is. The purpose is not just to avoid violating privacy (that could be achieved by outputting nothing); it's also to answer a query, and here we are talking about the accuracy of our estimate of the answer to the query. But again, it's a different question, so it doesn't belong here -- if after serious study you still don't understand, ask a new question. $\endgroup$ – D.W.♦ Jun 23 '15 at 21:26
Not the answer you're looking for? Browse other questions tagged complexity-theory cryptography information-theory or ask your own question.
What do we know about $NP \cap co-NP$?
How does hashing achieve sketching?
Where to start studying about HTM?
Relation between problems and algorithms
Gap between the average length of a Huffman code and its entropy
Relationship between message entropy and complexity of the best algorithm
Entropy notation: What does this mean?
What is the relation between NC and P/poly?
About the definition of "differential privacy" in communication complexity
Relation between Hamming distances of columns and rows
relation between ntime and dtime
Finding the Entropy of a random experiment with probability of $\frac{1}{3}$
What is the relation between the quantity of information of $A_i$ and $A$, where $A=\bigcup_iA_i$?
ROC of the function in the problem 9.14 of Oppenheim's Signals and Systems textbook