Score:2

Checking Independence of combination of uniform random variables to use pilling up lemma

br flag

My question is very basic one. Suppose $a_0, a_1, a_2, a_3, a_4, b_0, b_1, b_2, b_3, b_4$ are $10$ uniform random variables from $\{0,1\}$ independent of each other. Now there are expressions of the form

  1. $a_4b_4 + a_3(b_0 + b_2+1) + b_3(a_0 + a_2 +1) + a_1(b_2 + b_4) + b_1(a_2 +a_4)$
  2. $a_2b_0 + a_1b_1 + (a_0 + a_2 +1)b_2$

Can we apply Pilling up lemma? Or alternatively are the random variables $a_4b_4, a_3(b_0 + b_2+1), b_3(a_0 + a_2 +1), a_1(b_2 + b_4), b_1(a_2 +a_4)$ independent in case 1? Similarly are $a_2b_0 , a_1b_1 , (a_0 + a_2 +1)b_2$ independent in case 2 ?

How to show independence or dependency? Can anyone please help me understand these?

p.s - I can't find suitable tags other than linear-cryptoanalyzes. Anyone who can better tag the question is always welcome.

kelalaka avatar
in flag
The plus is x-or, rigth? You can use `\oplus` for this. And, note that Piling-Up lemma about x-oring not and. And is destructive and creates bias!.
hiren_garai avatar
br flag
yes the plus is x-or.
Score:1
cn flag

For $2$, it's easy to see these variables are independents because each elementary variables which appear in one of the expressions doesn't appear in the other.

For example

$\mathbb{P}(a_2b_0=0| a_1b_1=0, b_2(a_0 + a_2 +1)=0) = \mathbb{P}(a_4b_4=0)$.

A good way to see this, I think is to look the entropy of one of this variable :

$H (a_2 b_0 |a_1 b_1, b_2(a_0 + a_2 +1) ) \geq H (a_2 b_0 |a_0, a_1, b_1, b_2 ) = H (a_2 b_0 )$.

The last equality comes from the independence of the elementary variables.

Thus we can deduce $H (a_2 b_0 |a_1 b_1, b_2(a_0 + a_2 +1) )= H (a_2 b_0 ) $.

About $1$, it's more complex because $b_4, b_2, a_2, a_4$ appear in more than one expression.

Then you have to show that $a_4, b_4, a_3, (b_0 + b_2), b_3, (a_0 + a_2), a_1 ,(b_2 + b_4), b_1, (a_2 + a_4)$ are linearly independent in $\mathbb{F}_2$ (by doing linear algebra), thus you can deduce these variables (eventually plus a constant) are independents (from a probabilistic point of view).

And then you have to use the argument "if $X, Y, Z, T$ are independent, then $XY$ and $ZT$ are independents."

Edit : A good way to see the independence of the linear variables is to compute the determinant of the following matrix (the first line correspond to $a_4$, the second to $b_4$, the fourth to $b_0 + b_2$, etc), you can also proof these family of vector generates $\mathbb{F}^{10}_p$, and deduce by the cardinality, it's base, and thus the vectors are independents :

$\begin{matrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix}$

hiren_garai avatar
br flag
thank you for your elaborative answer. Entropy is a little bit advanced for me. The linear algebra part you suggested to use is basically to show that if $c_1a_4 + c_2b_4 + \cdots = 0$ holds then all the coefficients $c_1, c_2, ..$ are zero ?
Ievgeni avatar
cn flag
Yes. Exactly. That's it.
hiren_garai avatar
br flag
So then the coefficients of $(b_2 + b_4), (a_2 + a_4)..$ are to be broken right ? And then we have to use the fact that $b_2, b_4,...$ are linearly independent. In that way the random variables are linearly dependent as some of the coefficients with non zero value is coming. Am I wrong somewhere ?
Ievgeni avatar
cn flag
What do you mean by "broken right"?
hiren_garai avatar
br flag
Also what about the $+1$ part ? I meant its $a_2 +a_4 +1$ right. I am stumbling to understand. Can you clear it out ? Thank you
hiren_garai avatar
br flag
By broken I meant $c_1 a_4 + \cdots + c_k (a_2 + a_4) + \cdots = 0$ implies $(c_1 + c_k)a_4 +c_k a_2 + \cdots $ ?
Ievgeni avatar
cn flag
If $X$ and $Y$ are independent, then $X+1$ are independent. So you have to consider the homogeneous version of an equation to look the linear independence, but then when you can add "+1" without changing the probabilistic independence.
Ievgeni avatar
cn flag
You can do this to show the linear independence, but I've proposed to you two other techniques : Compute the determinant of the associate matrix, or prove it's a base of the vector space (by showing it generates all the canonical vector).
hiren_garai avatar
br flag
You meant $X+1$ and $Y+1$ or $X+1$ and $Y$ are independent ? Also that $c_1, c_2, ...$ is very understandable to me so that's why I am trying to show in that way.
Ievgeni avatar
cn flag
About the "+1" Both are true, because the variables are in $\{0, 1\}$, it's easy to see by considering the definition.
Ievgeni avatar
cn flag
So, if you use the $c_i$'s techniques, you can deduce that each coefficient of the $a_i$'s are zero, because the $a_i$'s and the $b_i$'s are linearly independent (they form the canonical base).
hiren_garai avatar
br flag
Yes. I have understood. Thanks for your time. Almost lightened up.
hiren_garai avatar
br flag
One more question, by the help conditional probability we can show that $X, Y$ independent then $X+1, Y$ is independent. Now we can show this independence also by showing $c_1 (X+1) +c_2(Y) = 0 \implies c_1 X + c_2 Y + c_1 = 0 $ from that we must have to $c_1 = 0 = c_2$, so from $c_1 X + c_2 Y = c_1$ can we say $c_1 = c_2 = 0 $ ? Because we have to assume $c_1 =0$ to use the independence of $X$ and $Y$. Is that true ? @levgeni
Ievgeni avatar
cn flag
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/126509/discussion-between-ievgeni-and-hiren-garai).
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.