Piling-up lemma
Encyclopedia
In cryptanalysis
, the piling-up lemma is a principle used in linear cryptanalysis
to construct linear approximation
to the action of block cipher
s. It was introduced by Mitsuru Matsui
(1993) as an analytical tool for linear cryptanalysis.
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 piling-up lemma for two binary variables.
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 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 p1 and p2 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
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.
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.
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
, the piling-up lemma is a principle used in linear cryptanalysis
Linear cryptanalysis
In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers...
to construct linear approximation
Linear approximation
In mathematics, a linear approximation is an approximation of a general function using a linear function . They are widely used in the method of finite differences to produce first order methods for solving or approximating solutions to equations.-Definition:Given a twice continuously...
to the action of block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
s. It was introduced by Mitsuru Matsui
Mitsuru Matsui
is a Japanese cryptographer and senior researcher for Mitsubishi Electric Company. While researching error-correcting codes in 1990, Matsui was inspired by Biham and Shamir's differential cryptanalysis, and discovered the technique of linear cryptanalysis, published in 1993. Differential and linear...
(1993) as an analytical tool for linear cryptanalysis.
Theory
The piling-up lemma allows the cryptanalyst to determine the probabilityProbability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
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 piling-up lemma for two binary variables.
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 we are dealing with are independent
Dependent and independent variables
The terms "dependent variable" and "independent variable" are used in similar but subtly different ways in mathematics and statistics as part of the standard terminology in those subjects...
; 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 p1 and p2 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
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.
Practice
In practice, the XHowever, 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.