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


$NS(a, b)$ is even
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?
The following apply to all DES Sboxes.


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.
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$.