Suppose I have a function $F(x_1,\ldots,x_n)$, where each $x_i$ is of $l$-bits security (suppose each $x_i$ is a binary string of length $l$). At the same time, suppose there are $n$ persons, each one having a value $x_i = b_i$.

I want to write down in a mathematical formula the following: "given $x_1=b_1$, $\ldots$, $x_{n-1}=b_{n-1}$, the output of $F$ is dependent of $x_n$ and is of $l$-bits security". I.e., if any $n-1$ persons plug in their values, there are $2^l$ possibilities for $F(b_1,\ldots,b_{n-1},x_n)$.

For example, consider the function $F(x_1,\ldots,x_n) = x_1$. The output of $F$ is only dependent on $x_1$. This function offers no security: if player 1 plugs $x_1=b_1$, there is one unique possibily for $F(x_1,\ldots,x_n)$ ($l=0$).

Second example (bit-wise sum). Consider $F(x_1,\ldots,x_n) = x_1 + \cdots + x_n \pmod{2}$. Given $x_1,\ldots,x_{n-1}$, the output depends on $x_n$ and is of $l$-bits security.

Now, returning to the question, I have an intuition that the formula that I want is

$$H(F(x_1,\ldots,x_n) | x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n) = H(h_i) \quad \forall i=1,\ldots,n$$

where $H$ is the Shannon Entropy.

Can someone point if I am in the right path and formally describe the formula that I am looking for and explain it?

Thanks in advance.


To be well defined as a function, you need to specify lengths of the $x_i$, which is not the same thing as their entropy. Also, the $H(h_i)$ in your equation should probably be $H(x_i).$

Let's assume each $x_i$ are binary vectors of length $n$ for concreteness. Then what you want in a more general version of this problem would be $$ \mathbb{H}(F(x_1,\ldots,x_n) | x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n) \geq \mathbb{H}(x_i) \quad \forall i=1,\ldots,n $$ which also takes care of the unequal entropy case for the different $x_i.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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