Editing Piling-up lemma

{{Short description|Principle used in linear cryptanalysis}}
In [[cryptanalysis]], the '''piling-up lemma''' is a principle used in [[linear cryptanalysis]] to construct [[linear approximation]]s to the action of [[block cipher]]s. It was introduced by [[Mitsuru Matsui]] (1993) as an analytical tool for linear cryptanalysis.<ref>{{cite book |doi=10.1007/3-540-48285-7_33 |chapter=Linear Cryptanalysis Method for DES Cipher |title=Advances in Cryptology – EUROCRYPT '93 |series=Lecture Notes in Computer Science |year=1994 |last1=Matsui |first1=Mitsuru |volume=765 |pages=386–397 |isbn=978-3-540-57600-6 |s2cid=533517 }}</ref> The lemma states that the bias (deviation of the [[expected value]] from 1/2) of a [[parity function|linear Boolean function]] (XOR-clause) of [[Dependent and independent variables|independent]] [[Bernoulli distribution|binary random variables]] is related to the product of the input biases:<ref>{{cite web |last1=Li |first1=Qin |last2=Boztaş |first2=S. |title=Extended Linear Cryptanalysis and Extended Piling-up Lemma |website=ISC Turkey |date=December 2007 |s2cid=5508314 |url=http://www.iscturkey.org/assets/files/2016/03/2007-49.pdf |archive-url=https://web.archive.org/web/20170117175343/http://www.iscturkey.org/assets/files/2016/03/2007-49.pdf |archive-date=2017-01-17}}</ref>

:<math>\epsilon(X_1\oplus X_2\oplus\cdots\oplus X_n)=2^{n-1}\prod_{i=1}^n \epsilon(X_i)</math>

or

:<math>I(X_1\oplus X_2\oplus\cdots\oplus X_n ) =\prod_{i=1}^n I(X_i)</math>

where <math>\epsilon \in [-\tfrac{1}{2}, \tfrac{1}{2}]</math> is the bias (towards zero<ref>The bias (and imbalance) may also be taken as an absolute value; if the bias with flipped sign (bias towards one) is used the lemma needs an additional (-1)^(n+1) sign factor in the right hand side.</ref>) and <math>I \in [-1, 1]</math> the ''imbalance'':<ref>{{cite book |doi=10.1007/3-540-49264-X_3 |chapter=A Generalization of Linear Cryptanalysis and the Applicability of Matsui's Piling-up Lemma |title=Advances in Cryptology – EUROCRYPT '95 |series=Lecture Notes in Computer Science |year=1995 |last1=Harpes |first1=Carlo |last2=Kramer |first2=Gerhard G. |last3=Massey |first3=James L. |volume=921 |pages=24–38 |isbn=978-3-540-59409-3 }}</ref><ref>{{cite book |doi=10.1007/3-540-46665-7_22 |chapter=The Piling-Up Lemma and Dependent Random Variables |title=Cryptography and Coding |series=Lecture Notes in Computer Science |year=1999 |last1=Kukorelly |first1=Zsolt |volume=1746 |pages=186–190 |isbn=978-3-540-66887-9 }}</ref>

:<math>\epsilon(X) = P(X=0) - \frac{1}{2}</math>
:<math>I(X) = P(X=0) - P(X=1) = 2 \epsilon(X)</math>.
Conversely, if the lemma does not hold, then the input variables are not independent.<ref>{{Cite web|last=Nyberg|first=Kaisa|date=February 26, 2008|title=Linear Cryptanalysis (Cryptology lecture)|url=http://www.tcs.hut.fi/Studies/T-79.5501/2008SPR/lectures/lecture5.pdf |website=Helsinki University of Technology, Laboratory for Theoretical Computer Science}}</ref>

== 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 <math>I(X \oplus Y)</math> is a [[Correlation coefficient|correlation]] measure of <math>X</math> and <math>Y</math>, equal to <math>P(X=Y)-P(X\ne Y)</math>; <math>I(X)</math> can be interpreted as the correlation of <math>X</math> with <math>0</math>.

== Expected value formulation ==
The piling-up lemma can be expressed more naturally when the random variables take values in <math>\{-1,1\}</math>. If we introduce variables <math>\chi_i = 1 - 2X_i = (-1)^{X_i}</math> (mapping 0 to 1 and 1 to -1) then, by inspection, the XOR-operation transforms to a product:

:<math>\chi_1\chi_2\cdots\chi_n = 1 - 2(X_1 \oplus X_2\oplus\cdots\oplus X_n) = (-1)^{X_1 \oplus X_2\oplus\cdots\oplus X_n}</math>

and since the [[expected value]]s are the imbalances, <math>E(\chi_i)=I(X_i)</math>, the lemma now states:

:<math>E\left(\prod_{i=1}^n \chi_i \right)=\prod_{i=1}^nE(\chi_i)</math>

which is [[Product distribution|a known property of the expected value for independent variables]].

For [[Dependent and independent variables|dependent variables]] the above formulation gains a (positive or negative) [[covariance]] term, thus the lemma does not hold. In fact, since two [[Bernoulli distribution|Bernoulli]] variables are independent if and only if they are uncorrelated (i.e. have zero covariance; see [[Uncorrelatedness (probability theory)|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:

:<math>X_1\oplus X_2\oplus\cdots\oplus X_n=0</math>

holds, where the ''X''{{'}}s are [[binary variable]]s (that is, bits: either 0 or 1).

Let ''P''(A) denote "the probability that A is true". If it equals [[probability one|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 <math>P(X_1 = 0)=p_1</math> and <math>P(X_2 = 0)=p_2</math>.

Now, we consider:

:<math>P(X_1 \oplus X_2 = 0)</math>

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

:<math>P(X_1=X_2)</math>

''X''<sub>1</sub> = ''X''<sub>2</sub> = 0 and ''X''<sub>1</sub> = ''X''<sub>2</sub> = 1 are [[mutually exclusive events]], so we can say

:<math>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)</math>

Now, we must make the central assumption of the piling-up lemma: the binary variables we are dealing with are '''[[Dependent and independent variables|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:

:{|
|-
|<math>P(X_1 \oplus X_2 = 0)</math>
|<math>=P(X_1=0)P(X_2=0)+P(X_1=1)P(X_2=1)</math>
|-
|
|<math>=p_1p_2 + (1-p_1)(1-p_2)</math>
|-
|
|<math>=p_1p_2 + (1-p_1-p_2+p_1p_2)</math>
|-
|
|<math>=2p_1p_2-p_1-p_2+1</math>
|}

Now we express the probabilities ''p''<sub>1</sub> and ''p''<sub>2</sub> as {{sfrac|1|2}} + ε<sub>1</sub> and {{sfrac|1|2}} + ε<sub>2</sub>, where the ε's are the probability biases &mdash; the amount the probability deviates from {{sfrac|1|2}}.

:{|
|-
|<math>P(X_1 \oplus X_2 = 0)</math>
|<math>=2(1/2+\epsilon_1)(1/2+\epsilon_2)-(1/2+\epsilon_1)-(1/2+\epsilon_2)+1</math>
|-
|
|<math>=1/2+\epsilon_1+\epsilon_2+2\epsilon_1\epsilon_2-1/2-\epsilon_1-1/2-\epsilon_2+1</math>
|-
|
|<math>=1/2+2\epsilon_1\epsilon_2</math>
|}

Thus the probability bias ε<sub>1,2</sub> for the XOR sum above is 2ε<sub>1</sub>ε<sub>2</sub>.

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

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

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 &mdash; equal to {{sfrac|1|2}}.

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

:<math>\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)</math>

we have

:<math>\varepsilon_{total}=(-1)^{n+1}\prod_{i=1}^n \varepsilon_i,</math>
 
adding random variables amounts to multiplying their (2nd definition) biases.

==Practice==
In practice, the ''X''s are approximations to the [[S-box]]es (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.

==See also==
*[[Variance#Properties|Variance]] of a sum of independent real variables

==References==
{{reflist}}

{{Cryptography navbox | block}}

[[Category:Cryptographic attacks]]
[[Category:Lemmas]]