World Library  
Flag as Inappropriate
Email this Article

Piling-up lemma

Article Id: WHEBN0000715186
Reproduction Date:

Title: Piling-up lemma  
Author: World Heritage Encyclopedia
Language: English
Subject: Linear cryptanalysis, WikiProject Cryptography, Cryptographic attacks, Lemmas, Hardware random number generator
Collection: Cryptographic Attacks, Lemmas
Publisher: World Heritage Encyclopedia

Piling-up lemma

In cryptanalysis, the piling-up lemma is a principle used in linear cryptanalysis to construct linear approximation to the action of block ciphers. It was introduced by Mitsuru Matsui (1993) as an analytical tool for linear cryptanalysis.


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

X_1\oplus X_2\oplus\cdots\oplus 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, where P(X_1 = 0)=p_1 and P(X_2 = 0)=p_2.

Now, we consider:

P(X_1 \oplus X_2 = 0)

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

P(X_1=X_2)=P(X_1=X_2=0) + P(X_1=X_2=1)=P(X_1=0, X_2=0) + P(X_1=1, X_2=1)

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:

P(X_1 \oplus X_2 = 0) =P(X_1=0)P(X_2=0)+P(X_1=1)P(X_2=1)\
=p_1p_2 + (1-p_1)(1-p_2)\
=p_1p_2 + (1-p_1-p_2+p_1p_2)\

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 ½.

P(X_1 \oplus X_2 = 0) =2(1/2+\epsilon_1)(1/2+\epsilon_2)-(1/2+\epsilon_1)-(1/2+\epsilon_2)+1\

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:

P(X_1\oplus X_2\oplus\cdots\oplus X_n=0)=1/2+2^{n-1}\prod_{i=1}^n \epsilon_i

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 \epsilon_i = P(X_i=1) - P(X_i=0), in fact minus two times the previous value. The advantage is that now with

\varepsilon_{total}= P(X_1\oplus X_2\oplus\cdots\oplus X_n=1)- P(X_1\oplus X_2\oplus\cdots\oplus X_n=0)

we have

\varepsilon_{total}=(-1)^{n+1}\prod_{i=1}^n \varepsilon_i,

adding random variables amounts to multiplying their (2nd definition) biases.


In practice, the Xs 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.


This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.