I came across the notion of information theoretic privacy in the paper of Yamamoto ("A source coding problem for sources with additional outputs to keep secret from the receiver or wiretappers "). The way this problem is formulated is as follows.

We have a random variable $X$ and a correlated random variable $Y$ with joint distribution $q(x,y)$. We want to keep $X$ as private as possible while sending $Y$ withing distortion $D$ with the least compression rate (like conventional rate distortion problem). The fundamental limit for the rate is $$R(D,L):=\inf_{p_{\hat{Y}|Y}\in\mathcal{P}(D,L)} I(Y;\hat{Y})$$ where $\mathcal{P}(D,L)$ is the collection of all joint distribution $p(x,y,\hat{y})$ such that $\sum_{\hat{y}}p(x,y,\hat{y})=q(x,y)$, $Ed(Y,\hat{Y})\leq D$ and $I(X; \hat{Y})\leq L$.

Now I want to look at this problem from different angle. Random variable $Y$ is generated from $X$ and $Z$ is generated from $Y$. The quantity to look at now is $$\sup \{D_1(P_X||P_Y), \text{while}~D_2(P_X||P_Z) \geq \gamma\}$$ where $D_1$ and $D_2$ are two different probability metrics.

My questions:

  1. Do you think it is a wise approach to modify the privacy problem?
  2. How to choose the probability metrics $D_1$ and $D_2$ as to make the first problem as special case of the second one?

Any idea is appreciated,


1 Answer 1


There is a large body of work on information-theoretic notions of secrecy, spread between the information theory and cryptography communities. For example, this Wikipedia page has lots of useful links: https://en.wikipedia.org/wiki/Information-theoretic_security

I also recommend the recent paper of Bellare, Tessaro and Vardy for a recent perspective on the state of the art: http://arxiv.org/abs/1201.2205

To answer your question more specifically, I would reply with a question: "What is the operational meaning of your new proposed privacy measure"?

For example, constraining the mutual information $I(\hat Y || X)\leq L$ means that, in variety of senses, $\hat Y$ conveys at most $L$ bits of information about $X$. When $L\ll 1$, this has an additional operational meaning. At that point, the variational distance between the joint distribution given by $p(x,\hat y)$ and the product of the marginal distributions given by $p(x)\cdot p(\hat y)$ goes to 0. When this variational distance is at most $\epsilon$ it means that we can replace $\hat Y$ with a new random variable that is independent of $X$, and the probability of every event will change by at most $\epsilon$. (Side note: Cryptographers generally prefer to impose a bound on the variational distance directly, rather than directly via the mutual information.)

So the answer to your question depends a lot on which distance measure you use, and which probability distributions you constrain. Just constraining the distance between $P_X$ and $P_Z$ may not carry much meaning, since we could make some change to $Z$ (say, flipping every bit of $Z$) that dramatically changes the distribution but does not change the information conveyed by $Z$. A more interesting requirement is to constrain the distance between $P_X$ and $P_{X|Z=z}$ (the conditional distribution on $X$ given a particular observed value $z$ of $Z$). [A bound on $I(X;\hat Y)$ does have this form, since $I(X; \hat Y)$ is the expected KL divergence between the marginal on $X$ and the conditional distribution on $X$ given $\hat Y = \hat y$.] If you want to propose a different measure, then you should ask yourself (or mathoverflow...) if you can provide such an interpretation.

  • $\begingroup$ Thanks a lot for your detailed and clear answer. Just one point: I dont think even $I(X;\hat{Y})\leq \epsilon$ can result in a good operational interpretation of privacy for $\epsilon>0$. Of course when $\epsilon=0$ we have the statistical independence. But what does the constraint $I(X;\hat{Y})\leq \epsilon$ imply rigorously? $\endgroup$ Commented Apr 29, 2016 at 0:36
  • $\begingroup$ By the way, when $||P_{X\hat{Y}}-P_XP_{\hat{Y}}||\leq \epsilon$, it does not necessarily imply that the variational distance between $P_{(\hat{Y})|X=x}$ and $P_{(\hat{Y})}$ is at most $\epsilon$. So I don't understand your statement that "we can replace $\hat{Y}$ with a new random variable that is independent of $X$, and the probability of every event will change by at most $\epsilon$." $\endgroup$ Commented Apr 29, 2016 at 0:36
  • $\begingroup$ If you use the L1 norm (which corresponds to variational distance), then $\|P_{AB} -P_A P_B\| = E_{b\sim B} \|P_A - P_{A|B=b}\|$, for any random variables $A$ and $B$. That is, a bound on $\|P_{AB} -P_A P_B\|$ implies a bound on the expected distance $\|P_A - P_{A|B=b}\|$ (where the expectation is taken over a random choice of $b\sim B$). $\endgroup$
    – Adam Smith
    Commented Apr 29, 2016 at 14:10
  • $\begingroup$ You asked: "But what does the constraint $I(X;\hat Y)\leq \epsilon$ imply rigorously?" By Pinsker's inequality, constraining $I(X;\hat Y)$ constrains the variational distance discussed in the previous comment. en.wikipedia.org/wiki/… $\endgroup$
    – Adam Smith
    Commented Apr 29, 2016 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.