# 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:

[itex]X_1\oplus X_2\oplus\cdots\oplus X_n=0[itex]

holds, where the X 's are binary variables (that is, bits: either 0 or 1).

Let P(A) denote "the probability of event A happening". 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.

[itex]P(X_1 = i)=\left\lbrace\begin{matrix}p_1 & \hbox{for }i=0 \\ 1-p_1 & \hbox{for }i=1\end{matrix}\right.[itex]
[itex]P(X_2 = j)=\left\lbrace\begin{matrix}p_2 & \hbox{for }j=0 \\ 1-p_2 & \hbox{for }j=1\end{matrix}\right.[itex]

Now, we consider:

[itex]P(X_1 \oplus X_2 = 0)[itex]

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

[itex]P(X_1=X_2)[itex]

X1 = X2 = 0 and X1 = X2 = 1 are mutually exclusive events, so we can say

[itex]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)[itex]

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:

 [itex]P(X_1 \oplus X_2 = 0)[itex] [itex]=P(X_1=0)P(X_2=0)+P(X_1=1)P(X_2=1)\ [itex] [itex]=p_1p_2 + (1-p_1)(1-p_2)\ [itex] [itex]=p_1p_2 + (1-p_1-p_2+p_1p_2)\ [itex] [itex]=2p_1p_2-p_1-p_2+1\ [itex]

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

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

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:

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

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

## 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

 Block ciphers edit  (https://search.academickids.com:443/encyclopedia/index.php?title=Template:Block_ciphers&action=edit) Algorithms: 3-Way | AES | Akelarre | Blowfish | Camellia | CAST-128 | CAST-256 | CMEA | DEAL | DES | DES-X | FEAL | FOX | FROG | G-DES | GOST | ICE | IDEA | Iraqi | KASUMI | KHAZAD | Khufu and Khafre | LOKI89/91 | LOKI97 | Lucifer | MacGuffin | Madryga | MAGENTA | MARS | MISTY1 | MMB | NewDES | RC2 | RC5 | RC6 | REDOC | Red Pike | S-1 | SAFER | SEED | Serpent | SHACAL | SHARK | Skipjack | Square | TEA | Triple DES | Twofish | XTEA Design: Feistel network | Key schedule | Product cipher | S-box | SPN   Attacks: Brute force | Linear / Differential cryptanalysis | Mod n | XSL   Standardisation: AES process | CRYPTREC | NESSIE   Misc: Avalanche effect | Block size | IV | Key size | Modes of operation | Piling-up lemma | Weak key
##### Navigation

Academic Kids Menu

• Art and Cultures
• Art (http://www.academickids.com/encyclopedia/index.php/Art)
• Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
• Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
• Music (http://www.academickids.com/encyclopedia/index.php/Music)
• Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
• Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
• Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
• Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
• Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
• Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
• History (http://www.academickids.com/encyclopedia/index.php/History)
• Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
• Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
• Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
• Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
• Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
• Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
• United States (http://www.academickids.com/encyclopedia/index.php/United_States)
• Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
• World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
• Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
• Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
• Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
• Science (http://www.academickids.com/encyclopedia/index.php/Science)
• Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
• Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
• Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
• Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
• Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
• Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
• Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
• Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
• Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
• Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
• Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
• Government (http://www.academickids.com/encyclopedia/index.php/Government)
• Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
• Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
• Space and Astronomy
• Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
• Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
• Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
• Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
• Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
• US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

• Home Page (http://academickids.com/encyclopedia/index.php)
• Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

• Clip Art (http://classroomclipart.com)