# Derive a theoretical bound about coding with a partial eavesdropper

This post is improved from Determine binary function $f(x)$ by partial observation of $x$. Since the form of the problem is changed in a great extent. I would like to create a new post rather than edit the old one. If it is inappropriate, feel free to edit these two.

Let us start with some random variables $X_1, \dots, X_n$ and $Y$. Suppose Alice wants to transmit $Y$ to Bob by using $n$ communication channels. She does this by directly sending $X_i$ through the $i$-th channel respectively. Of course, the fact that this coding is correct gives us $$H(Y|X_1,\dots,X_n)=0$$ Now, here is an eavesdropper Eve. She can observe random $k$ channels out of $n$. In other words, she will know random $k$ variables out of $X_1,\dots,X_n$. Suppose the coding scheme can guarantee that Eve will not gain too more information about $Y$, by $$\frac{1}{\binom{n}{k}} \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}} I(Y; (X_i : i \in A)) \leq \epsilon$$ Then we can derive a bound about $\sum_{i=1}^n H(X_i)$: $$\frac{1}{n}\sum_{i=1}^n H(X_i) \geq \frac{1}{(n-k)\binom{n}{k}} \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}} H((X_i:i \notin A)) \\ \geq \frac{1}{(n-k)\binom{n}{k}} \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}} I(Y;(X_i:i \notin A) | (X_i:i \in A)) \\ = \frac{1}{(n-k)\binom{n}{k}} \sum_{\substack{A \subseteq \{1,\dots,n\} \\ |A|=k}} \left( I(Y;X_1,\dots,X_n) - I(Y;(X_i:i \in A)) \right) \\ =\frac{1}{n-k}(H(Y)-\epsilon)$$ My question:

Is this bound tight or asymptotic optimal? Is there any reference related to this problem, since it seems to be quite natural?

Trivial result. For $k = n-1$ and $\epsilon=0$, the bound is tight. For a construction one can refer to here.

Result from Xitip. I have used Xitip to verify the inequality where $n \leq 5$. I found that when I slightly increase the coefficient ($1/(n-k)$), the program reported that it would be no longer a Shannon-type inequality. This fact suggests that if the bound is not tight, we may find a family of new non-Shannon-type inequalities.

Cross-posted at https://cstheory.stackexchange.com/questions/39102/.

## 1 Answer

(comment) If all subsets of size k leak $\frac{\epsilon}{n}$ bits, then you are looking at threshold (secret-sharing) schemes. In that specific case, it is tight: the bound is the threshold gap and the construction is a ramp scheme. Your leak condition being quite loose, other structures usually require a different bound (possibly with non-Shannon-type inequalities).

• @Lwins.Gafield: maybe ajc.maths.uq.edu.au/pdf/14/ajc-v14-p51.pdf can help. Alos, Example 2.9 in eprint.iacr.org/2014/124.pdf – Tarik Kaced Sep 18 '17 at 10:52
• tl;dr: No, not in general. If $Y$ is not uniformly distributed, little is known. You can replace Y by typical values of $M$ i.i.d. copies to make it quasi-uniform and the result should still hold. Otherwise, if dealing with general $Y$, our paper shows a general construction which is exponential in $n$, how to improve these scheme is a major open question. – Tarik Kaced Sep 18 '17 at 13:58
• For basics, you should start by learning about Shamir's scheme, then modify it to get a ramp scheme (what you want). As for binary random variables, I think you need at least as many values as the number of variables for a ramp scheme. A new result proves you need at least log n values (but this is state-of-the-art stuff) – Tarik Kaced Sep 18 '17 at 15:37
• Yes, the same $n$, but this is specific to ramp schemes. In general, it is not known. Do you have a construction for any $\epsilon$ and (uniform) binary $Y$ ? – Tarik Kaced Sep 18 '17 at 16:42
• Indeed, I wasn't clear. You would need log(n) bits, more details can be found in eccc.weizmann.ac.il/report/2016/131/download – Tarik Kaced Sep 18 '17 at 17:00