The lemma Piling-Up is a statistical result introduced by Mitsuru Matsui in 1993 within the framework of the linear Cryptanalyse. This lemma makes it possible to quantify statistical skew present in a linear approximation of a symmetrical encryption algorithm per block.

Mathematical formulation

A linear equation within the framework of the linear cryptanalyse is appeared as exclusive-OR binary variables:

$X\_1\; \backslash \; oplus\; X\_2\; \backslash \; oplus\dots \; \backslash \; oplus\; X\_N\; =\; 0$

Either $N~$ random variable, independent and binary (the result of the event is or 0, or 1), $X\_1,\; X\_2,\dots ,\; X\_N~$, probability that this equation or correct is:

$P\; (X\_1\; \backslash \; oplus\; X\_2\; \backslash \; oplus\dots \; \backslash \; oplus\; X\_N\; =\; 0)\; =\; 1/2\; +\; 2^\; \{N-1\}\; \backslash \; prod\_\; \{i=1\}\; ^\; \{NR\}\; \backslash \; epsilon\_i$

with $\backslash \; epsilon\_i~$, the linear skew of the random variable $X\_i~$. This skew can be positive or negative and quantifies the variation compared to a uniform Distribution where the hope of a binary random variable is 1/2. The more important skew is, the more one encryption algorithm is likely to be attacked via the linear cryptanalyse.

Reasoning

Either $P\; (A)~$, the probability that the event has arrives. With a probability of 1, the event will occur. Conversely, a probability of 0 indicates the impossibility of this event. Within the framework of the Piling-Up lemma, we thus have business with random variables, binary and considered as independent.

Let us consider initially the lemma for two random variables:

Now let us consider the probability of a linear equation with these two variables:

$P\; (X\_1\; \backslash \; oplus\; X\_2\; =\; 0)$

Thanks to the properties of XOR, this is equivalent to:

$P\; (X\_1=X\_2)\; ~$

X ₁ = X ₂ = 0 and X ₁ = X ₂ = 1 is events mutually excluded and from this fact:

$P\; (X\_1=X\_2)\; =P\; (X\_1=X\_2=0)\; +\; P\; (X\_1=X\_2=1)\; =P\; (X\_1=0,\; X\_2=0)\; +\; P\; (X\_1=1,\; X\_2=1)\; ~$

We leave consequently the principle which the variables are independent. I.e. the state of a variable will not influence the state of another. One can thus extend the probability to the following result:

We express now the probabilities p ₁ and p ₂ like ½ + ε₁ and ½ + ε₂, where the ε are skews of probabilities - the quantity of deviation of the probability compared to ½.

Thus, skew ε_1,2 for the sum of XOR above is of 2ε₁ε₂.

This formula can extend for an infinite number of variables as follows:

$P\; (X\_1\; \backslash \; oplus\; X\_2\; \backslash \; oplus\; \backslash \; cdots\; \backslash \; oplus\; X\_n=0)\; =1/2+2^\; \{n-1\}\; \backslash \; prod\_\; \{i=1\}\; ^n\; \backslash \; epsilon\_i$

If a ε is to zero, i.e. one of the variables not-is skewed, then the whole of the function will not be skewed and equalizes with ½.

See too

• Cryptanalyse differential

Random links:

Dražan Jerković | Ceridwen (first name) | Roll | Saola | Ivvavik national park