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:

or

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

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

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 ${\displaystyle I(X\oplus Y)}$ is a correlation measure of ${\displaystyle X}$ and ${\displaystyle Y}$, equal to ${\displaystyle P(X=Y)-P(X\neq Y)}$; ${\displaystyle I(X)}$ can be interpreted as the correlation of ${\displaystyle X}$ with ${\displaystyle 0}$.

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

and since the expected values are the imbalances, ${\displaystyle E(\chi _{i})=I(X_{i})}$, the lemma now states: