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 is the bias (towards zero) and the imbalance: . 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 is a correlation measure of and , equal to ; can be interpreted as the correlation of with . Expected value formulation The piling-up lemma can be expressed more naturally when the random variables take values in . If we introduce variables (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, , the lemma now states: 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: holds, where the Xs 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 piling-up lemma for two binary variables, where and . Now, we consider: Due to the properties of the xor operation, this is equivalent to X1 = X2 = 0 and X1 = X2 = 1 are mutually exclusive events, so we can say Now, we must make the central assumption of the piling-up lemma: the binary variables