# Piling-up lemma

Piling-up lemma

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.

Theory

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

:$X_1oplus X_2opluscdotsoplus X_n=0$

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:

:$P\left(X_1 oplus X_2 = 0\right)$

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

:$P\left(X_1=X_2\right)$

"X"1 = "X"2 = 0 and "X"1 = "X"2 = 1 are mutually exclusive events, so we can say

:$P\left(X_1=X_2\right)=P\left(X_1=X_2=0\right) + P\left(X_1=X_2=1\right)=P\left(X_1=0, X_2=0\right) + P\left(X_1=1, X_2=1\right)$

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 "p"1 and "p"2 as ½ + &epsilon;1 and ½ + &epsilon;2, where the &epsilon;'s are the probability biases &mdash; the amount the probability deviates from ½.

Thus the probability bias &epsilon;1,2 for the XOR sum above is 2&epsilon;1&epsilon;2.

This formula can be extended to more "X" 's as follows:

:$P\left(X_1oplus X_2opluscdotsoplus X_n=0\right)=1/2+2^\left\{n-1\right\}prod_\left\{i=1\right\}^n epsilon_i$

Note that if any of the &epsilon;'s is zero; that is, one of the binary variables is unbiased, the entire probability function will be unbiased &mdash; equal to ½.

A related slightly different definition of the bias is$epsilon_i = P\left(X_i=1\right) - P\left(X_i=0\right),$ in fact minus two times the previous value. The advantage is that now with

$varepsilon_\left\{total\right\}= P\left(X_1oplus X_2opluscdotsoplus X_n=1\right)- P\left(X_1oplus X_2opluscdotsoplus X_n=0\right)$

we have

:$varepsilon_\left\{total\right\}=prod_\left\{i=1\right\}^n varepsilon_i,$ adding random variables amounts to multiplying their (2nd definition) biases.

Practice

In practice, the "X"s are approximations to the S-boxes (substitution components) of block ciphers. Typically, "X" values are inputs to the S-box and "Y" 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.

References

* Mitsuru Matsui. Linear Cryptanalysis Method for DES Cipher. EUROCRYPT 1993: 386-397

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• List of lemmas — This following is a list of lemmas (or, lemmata , i.e. minor theorems, or sometimes intermediate technical results factored out of proofs). See also list of axioms, list of theorems and list of conjectures. 0 to 9 *0/1 Sorting Lemma ( comparison… …   Wikipedia

• Линейный криптоанализ — В криптографии линейным криптоанализом называется метод криптоаналитического вскрытия, использующий линейные приближения для описания работы шифра. Линейный криптоанализ был изобретён японским криптологом Мицуру Мацуи (Mitsuru Matsui).… …   Википедия

• List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

• 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. Linear cryptanalysis is one of the two… …   Wikipedia

• Атака на основе адаптивно подобранного открытого текста — вид атаки в криптоанализе, предполагающая, что криптоаналитик может выбирать открытый текст и получать соответствующий ему шифртекст. Цель криптоаналитика получить возможность извлекать информацию из перехваченных шифртекстов этой системы, а в… …   Википедия

• 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 (for example) a 128 bit block of plaintext as… …   Wikipedia

• Data Encryption Standard — The Feistel function (F function) of DES General Designers IBM First publis …   Wikipedia

• Differential cryptanalysis — is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at… …   Wikipedia

• International Data Encryption Algorithm — IDEA An encryption round of IDEA General Designers Xuejia Lai and James Massey …   Wikipedia

• Triple DES — Triple Data Encryption Algorithm General First published 1998 (ANS X9.52) Derived from DES Cipher detail Key sizes 168, 112 or 56 bits (Keying option 1, 2, 3 respectively) Block sizes …   Wikipedia