Editing Piling-up lemma (section)

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