Piling Up Lemma

Tags: cryptography proof

\begin{align} \label{eq:matsui-lemma} P(X_1 \xor X_2 \xor ... \xor X_n = 0) = \frac{1}{2} + 2^{n-1} \prod^{n}_ \epsilon_i \end{align}

Where:

\( X_i \) is a random variable with possible values \( \{0,1\} \) whose value is independent of all other random variables \( X_n \forall n \in \mathbb{Z} \land n \ne i \).
\( p(x=0) \) the probability of the random variable \( x \) being \( 0 \)
\( \epsilon_i \) is the bias of the random variable \( i \).

Proof

Works by creating two random variables \( X_1, X_2 \) matching the description above with the definition for \( P(X_i=j) \) being:

\begin{align} \label{eq:random-prob} P(X_i=j) = \begin{cases}

p\_i       & \text{if $j = 0$} \\\\
(1 - p\_i) & \text{if $j = 1$} \\\\

\end{cases} \end{align}

Now consider the [see page 8, equation]:

\begin{align} \label{eq:prob-combined} P(X_1 \xor X_2=0) = P(X_1=0)P(X_2=0) + P(X_1=1)P(X_2=1) \end{align}

Here we've just expanded the definition of XOR, where the output is 0 only when both inputs are 0 or both inputs are 1.

If we substitute eq:random-prob into eq:prob-combined, we get:

\begin{align*} P(X_1 \xor X_2 = 0) &= P(X_1 = X_2) \\

                  &= P(X\_1 = 0)P(X\_2 = 0) + P(X\_1 = 1) P(X\_2 = 1) \\\\
                  &= p\_1 p\_2 + (1-p\_1)(1-p\_2)

\end{align*}

Now if we redefine \( p_i \) in terms of the bias \( \epsilon_i \) from the unbiased value of \( \frac{1}{2} \) we get: \[ p_i = \frac{1}{2} + \epsilon_i \]

\begin{align*} P(X_1 \xor X_2) &= (\frac{1}{2} + \epsilon_1) (\frac{1}{2} + \epsilon_2) + (1 - (\frac{1}{2} + \epsilon_1))(1 - (\frac{1}{2} + \epsilon_2)) \\

              &= (\frac{1}{4} + \frac{\epsilon\_1}{2} + \frac{\epsilon\_2}{2} + \epsilon\_1 \epsilon\_2) + (\frac{1}{2} - \epsilon\_1)(\frac{1}{2} - \epsilon\_2) \\\\
              &= (\frac{1}{4} + \frac{\epsilon\_1}{2} + \frac{\epsilon\_2}{2} + \epsilon\_1 \epsilon\_2) + (\frac{1}{4} - \frac{\epsilon\_1}{2} - \frac{\epsilon\_2}{2} + \epsilon\_1 \epsilon\_2) \\\\
              &= \frac{1}{2} + 2 \epsilon\_1 \epsilon\_2

\end{align*}

TODO: Explain extra derivation.

This derivation can be [see page 8, extended] for \( i > 2 \).

Links to this note

Linear Cryptanalysis