Piling-up lemma

In <a href="/facts/Cryptanalysis/7CPEQlJI">cryptanalysis</a>, the piling-up lemma is a principle used in <a href="/facts/Linear_cryptanalysis/Hvg2bJpC">linear cryptanalysis</a> to construct <a href="/facts/Linear_approximation/SDBAneFx">linear approximations</a> to the action of <a href="/facts/Block_cipher/MJywAyfQ">block ciphers</a>. It was introduced by <a href="/facts/Mitsuru_Matsui/dkteBCbI">Mitsuru Matsui</a> (1993) as an analytical tool for linear cryptanalysis. The lemma states that the bias (deviation of the <a href="/facts/Expected_value/1XV0JKL8">expected value</a> from 1/2) of a <a href="/facts/Parity_function/VHXnG1uf">linear Boolean function</a> (XOR-clause) of <a href="/facts/Dependent_and_independent_variables/dINfzIF2">independent</a> <a href="/facts/Bernoulli_distribution/ChCtYyvs">binary random variables</a> is related to the product of the input biases:

ϵ
        (
        
          X
          
            1
          
        
        ⊕
        
          X
          
            2
          
        
        ⊕
        ⋯
        ⊕
        
          X
          
            n
          
        
        )
        =
        
          2
          
            n
            −
            1
          
        
        
          ∏
          
            i
            =
            1
          
          
            n
          
        
        ϵ
        (
        
          X
          
            i
          
        
        )
      
    
    {\displaystyle \epsilon (X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=2^{n-1}\prod _{i=1}^{n}\epsilon (X_{i})}

or

I
        (
        
          X
          
            1
          
        
        ⊕
        
          X
          
            2
          
        
        ⊕
        ⋯
        ⊕
        
          X
          
            n
          
        
        )
        =
        
          ∏
          
            i
            =
            1
          
          
            n
          
        
        I
        (
        
          X
          
            i
          
        
        )
      
    
    {\displaystyle I(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=\prod _{i=1}^{n}I(X_{i})}

where 
 
 
 
 ϵ
 ∈
 [
 −
 
 
 
 1
 2
 
 
 
 ,
 
 
 
 1
 2
 
 
 
 ]
 
 
 {\displaystyle \epsilon \in [-{\tfrac {1}{2}},{\tfrac {1}{2}}]}
 
 is the bias (towards zero) and 
 
 
 
 I
 ∈
 [
 −
 1
 ,
 1
 ]
 
 
 {\displaystyle I\in [-1,1]}
 
 the imbalance:

ϵ
        (
        X
        )
        =
        P
        (
        X
        =
        0
        )
        −
        
          
            1
            2
          
        
      
    
    {\displaystyle \epsilon (X)=P(X=0)-{\frac {1}{2}}}

I
 (
 X
 )
 =
 P
 (
 X
 =
 0
 )
 −
 P
 (
 X
 =
 1
 )
 =
 2
 ϵ
 (
 X
 )
 
 
 {\displaystyle I(X)=P(X=0)-P(X=1)=2\epsilon (X)}
 
.
Conversely, if the lemma does not hold, then the input variables are not independent.

Piling-up lemma open-in-new

Piling-up lemma