2
$\begingroup$

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/.

$\endgroup$

1 Answer 1

1
$\begingroup$

(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).

$\endgroup$
11
  • 1
    $\begingroup$ @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 $\endgroup$ Sep 18, 2017 at 10:52
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 18, 2017 at 13:58
  • 1
    $\begingroup$ 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) $\endgroup$ Sep 18, 2017 at 15:37
  • 1
    $\begingroup$ 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$ ? $\endgroup$ Sep 18, 2017 at 16:42
  • 1
    $\begingroup$ 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 $\endgroup$ Sep 18, 2017 at 17:00

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.