Piling-up lemma

Template:Short description In cryptanalysis, the piling-up lemma is a principle used in linear cryptanalysis to construct linear approximations to the action of block ciphers. It was introduced by Mitsuru Matsui (1993) as an analytical tool for linear cryptanalysis. The lemma states that the bias (deviation of the expected value from 1/2) of a linear Boolean function (XOR-clause) of independent binary random variables is related to the product of the input biases:

$\epsilon (X_1\oplus X_2\oplus \cdots \oplus X_n)=2^{n-1}\prod _{i=1}^n\epsilon (X_i)$

or

$I(X_1\oplus X_2\oplus \cdots \oplus X_n)=\prod _{i=1}^{n}I(X_i)$

where $\epsilon \in [-\frac{1}{2},\frac{1}{2}]$ is the bias (towards zero) and $I\in [-1,1]$ the imbalance:

$\epsilon (X)=P(X=0)-\frac{1}{2}$

$I(X)=P(X=0)-P(X=1)=2\epsilon (X).$

Conversely, if the lemma does not hold, then the input variables are not independent.

Interpretation

The lemma implies that XOR-ing independent binary variables always reduces the bias (or at least does not increase it); moreover, the output is unbiased if and only if there is at least one unbiased input variable.

Note that for two variables the quantity $I(X\oplus Y)$ is a correlation measure of $X$ and Template:Tmath, equal to Template:Tmath; $I(X)$ can be interpreted as the correlation of $X$ with Template:Tmath.

Expected value formulation

The piling-up lemma can be expressed more naturally when the random variables take values in Template:Tmath. If we introduce variables ${\chi }_i=1-2X_i=(-1{)}^{X_i}$ (mapping Template:Tmath to Template:Tmath and Template:Tmath to Template:Tmath) then, by inspection, the XOR-operation transforms to a product:

${\chi }_1{\chi }_2\cdots {\chi }_n=1-2(X_1\oplus X_2\oplus \cdots \oplus X_n)=(-1{)}^{X_1\oplus X_2\oplus \cdots \oplus X_n}$

and since the expected values are the imbalances, Template:Tmath, the lemma then states:

$E\left(\prod _{i=1}^n{\chi }_i\right)=\prod _{i=1}^{n}E({\chi }_i),$

which is a known property of the expected value for independent variables.

For dependent variables the above formulation gains a (positive or negative) covariance term, thus the lemma does not hold. In fact, since two Bernoulli variables are independent if and only if they are uncorrelated (i.e. have zero covariance; see uncorrelatedness), we have the converse of the piling up lemma: if it does not hold, the variables are not independent (uncorrelated).

Boolean derivation

The piling-up lemma allows the cryptanalyst to determine the probability that the equality:

$X_1\oplus X_2\oplus \cdots \oplus X_n=0$

holds, where the Template:Tmaths are binary variables (that is, bits: either Template:Tmath or Template:Tmath).

Let Template:Tmath denote "the probability that Template:Tmath is true". If it equals one, Template:Tmath is certain to happen, and if it equals zero, Template:Tmath cannot happen. First of all, we consider the piling-up lemma for two binary variables, where $P(X_1=0)=p_1$ and Template:Tmath.

Now, we consider:

$P(X_1\oplus X_2=0).$

Due to the properties of the xor operation, this is equivalent to

$P(X_1=X_2).$

Template:Tmath and Template:Tmath are mutually exclusive events, so we can say

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

Now, we must make the central assumption of the piling-up lemma: the binary variables we are dealing with are independent; that is, the state of one has no effect on the state of any of the others. Thus we can expand the probability function as follows:

$P(X_1\oplus X_2=0)$	$=P(X_1=0)P(X_2=0)+P(X_1=1)P(X_2=1)$
	$=p_1{p}_2+(1-p_1)(1-p_2)$
	$=p_1{p}_2+(1-p_1-p_2+p_1{p}_2)$
	$=2p_1{p}_2-p_1-p_2+1$

Now we express the probabilities Template:Tmath and Template:Tmath as Template:Tmath and Template:Tmath, where the Template:Tmaths are the probability biases – the amount the probability deviates from Template:Tmath.

$P(X_1\oplus X_2=0)$	$=2(1/2+{\epsilon }_1)(1/2+{\epsilon }_2)-(1/2+{\epsilon }_1)-(1/2+{\epsilon }_2)+1$
	$=1/2+{\epsilon }_1+{\epsilon }_2+2{\epsilon }_1{\epsilon }_2-1/2-{\epsilon }_1-1/2-{\epsilon }_2+1$
	$=1/2+2{\epsilon }_1{\epsilon }_2$

Thus the probability bias Template:Tmath for the XOR sum above is Template:Tmath.

This formula can be extended to more Template:Tmaths as follows:

$P(X_1\oplus X_2\oplus \cdots \oplus X_n=0)=1/2+2^{n-1}\prod _{i=1}^n{\epsilon }_i$

Note that if any of the Template:Tmaths is zero; that is, one of the binary variables is unbiased, the entire probability function will be unbiased – equal to Template:Tmath.

A related slightly different definition of the bias is Template:Tmath, in fact minus twice the previous value. The advantage is that now with

${\epsilon }_{\text{total}}=P(X_1\oplus X_2\oplus \cdots \oplus X_n=1)-P(X_1\oplus X_2\oplus \cdots \oplus X_n=0)$

we have

${\epsilon }_{\text{total}}=(-1{)}^{n+1}\prod _{i=1}^n{\epsilon }_i,$

adding random variables amounts to multiplying their (2nd definition) biases.

Practice

In practice, the Template:Tmaths are approximations to the S-boxes (substitution components) of block ciphers. Typically, Template:Tmath values are inputs to the S-box and Template:Tmath values are the corresponding outputs. By simply looking at the S-boxes, the cryptanalyst can tell what the probability biases are. The trick is to find combinations of input and output values that have probabilities of zero or one. The closer the approximation is to zero or one, the more helpful the approximation is in linear cryptanalysis.

However, in practice, the binary variables are not independent, as is assumed in the derivation of the piling-up lemma. This consideration has to be kept in mind when applying the lemma; it is not an automatic cryptanalysis formula.

See also

• Template:Slink – Variance of a sum of independent real variables