In cryptanalysis, the pilingup 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 pilingup lemma allows the cryptanalyst to determine the probability that the equality:
holds, where the X 's are binary variables (that is, bits: either 0 or 1).
Let P(A) denote "the probability that A is true". If it equals one, A is certain to happen, and if it equals zero, A cannot happen. First of all, we consider the pilingup lemma for two binary variables.
Now, we consider:
Due to the properties of the xor operation, this is equivalent to
X_{1} = X_{2} = 0 and X_{1} = X_{2} = 1 are mutually exclusive events, so we can say
Now, we must make the central assumption of the pilingup 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:
Now we express the probabilities p_{1} and p_{2} as ½ + ε_{1} and ½ + ε_{2}, where the ε's are the probability biases — the amount the probability deviates from ½.
Thus the probability bias ε_{1,2} for the XOR sum above is 2ε_{1}ε_{2}.
This formula can be extended to more X 's as follows:
Note that if any of the ε's is zero; that is, one of the binary variables is unbiased, the entire probability function will be unbiased — equal to ½.
A related slightly different definition of the bias is ε_{i} =
P(X_{i} = 1) −
P(X_{i} = 0), in fact
minus two times the previous value. The advantage is that now
with
we have
adding random variables amounts to multiplying their (2nd definition) biases.
In practice, the Xs are approximations to the Sboxes (substitution components) of block ciphers. Typically, X values are inputs to the Sbox and Y values are the corresponding outputs. By simply looking at the Sboxes, 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 pilingup lemma. This consideration has to be kept in mind when applying the lemma; it is not an automatic cryptanalysis formula.
