# Expected vs actual amount of information leaked by an $l$-bits message

Say we have a random variable $$X$$ that contains $$k$$ bits of information, and a message $$M = f(X)$$ ($$M$$ is deterministic given $$X$$) that is $$l$$ bits long, where $$l. This implies $$H(X) = k$$ and $$H(M) \le l$$. Hence, we know on average $$M$$ leaks at most $$l$$ bits of information about $$X$$:

$$H(X \mid M) = H(X) - I(X;M) \geq H(X) - H(M) \geq k - l$$.

Now, can we get an upper bound to the probability (over $$X$$) that $$M$$ leaks $$l + t$$ bits of information about $$X$$, or $$\Pr_{M}[H(X) - H(X \mid M = m) \geq l + t]$$?

Obviously, we can use Markov inequality to bound the probability down to $$\epsilon$$ when $$t = (1/\epsilon - 1)l$$. But can we get something better, or even something as good as $$2^{-t}$$?

This sounds like something really basic when you want to talk about deterministic protocol on random input, but I cannot find material that talks about this... Many thanks in advance.

• Hm, so how about a distribution where $M = X$ with probability $l/k$, otherwise $M$ is null. – usul Jun 7 '19 at 17:45
• I don't think you can encode $l/k$ fraction of $X$ with only $l$ bits. You need at least $\log (2^{k} l/k)$ for that. – Dawei Huang Jun 7 '19 at 19:41
• Intuitively, you only need that many bits with probability $l/k$, otherwise you need $O(1)$ bits, so the average number of bits used is still $\approx l$. More formally, let $X$ be uniform on $\{1,...,2^k\}$. Let $M = X$ if $X \leq \frac{l-1}{k}2^k$, otherwise $M=0$. Then $H(X) = k$ while $H(M) \leq l$ by my calculations. – usul Jun 9 '19 at 17:47
• @usul: If $M=X$ for $X \leq \frac{l-1}{k} 2^k$, then you need $\frac{l-1}{k}2^k \leq 2^l$. Or $\frac{l-1}{k}\leq 2^{-(k-l)}$. Which means that $k$ is pretty close to $l$. – Peter Shor Jun 10 '19 at 1:40
• How about the following case: $X$ takes the all-zeroes string of length with probability 0.5, otherwise it is uniformly distributed over all strings of length $n$ except the all-zeroes string. $M$ is $0$ if $X$ is the all-zeroes string, and $1$ otherwise. In this case, the entropy of $X$ is roughly $n/2$, but conditioned on $M = 0$, its probability drops to $0$. Hence, if we take $l = 1, t = \frac{n}{2} - 1$, the probability over $m$ that conditioning on $M = m$ makes the entropy of $X$ drop by more than $l + t$ is $0.5 \gg 2^{-t}$. – Or Meir Jun 11 '19 at 12:12