# Matsui's Linear Cryptanalysis Lemma 1

In Matsui's paper (Linear Cryptanalysis Method for DES cipher), lemma 1.

1. $$NS(a, b)$$ is even
2. if $$a=1,32$$,or $$33$$, then $$NS(a,b)=32$$ for all $$b$$

He said that the following lemma is now trivial from the definition of S-boxes.

• But I can't prove this lemma. How can I prove this lemma?

1. Note that $$\overline{a}\cdot \overline{x}$$ and $$\overline{b}\cdot \overline{S(x)}$$ are both linear boolean functions which thus have truth tables with even Hamming weight. The xor of the two quantities is also even, since if they have hamming distance $$d$$ this is 64 minus (the difference of two even hamming weights) by inclusion exclusion.
2. The $$a=1,32,33$$ masking patterns are the ones where either LSB or MSB or both of input bits in the corresponding vector $$\overline{a}$$ are set to one while the remaining bits are set to zero. Recall that for each of the four such possibilities ($$a=0$$ as well) the DES Sbox output is a permutation of four bits. This also gives a balanced hamming weight, for all output masks $$b$$.