# Finding Linear Redundancy by counting the number of distinct frequency distributions of absolute walsh transform

I am writing a program to find linear redundancy in 4x4 s boxes. Is the number of distinct frequency distributions of absolute walsh transform a direct measure of linear redundancy in s boxes?

byte[] S = new byte[16]{0x1 ,0xB ,0x9 ,0xC ,0xD ,0x6 ,0xF ,0x3 ,0xE ,0x8 ,0x7 ,0x4 ,0xA ,0x2 ,0x5 ,0x0}; //E Mini-box of Whirlpool

The absolute coefficients of walsh transform is given below:

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
4,4,0,0,4,4,0,8,4,4,0,8,4,4,0
4,4,0,4,0,0,4,4,0,0,4,8,4,4,8
0,0,8,4,4,4,4,4,4,4,4,0,8,0,0
4,0,4,4,0,4,0,0,4,8,4,4,0,4,8
8,4,4,4,4,8,0,0,0,4,4,4,4,0,0
0,4,4,0,8,4,4,4,4,0,0,4,4,8,0
4,8,4,0,4,0,4,4,0,4,0,4,8,4,0
4,0,4,0,4,0,4,8,4,8,4,0,4,0,4
0,4,4,8,0,4,4,0,8,4,4,0,0,4,4
8,4,4,4,4,0,8,4,4,0,0,0,0,4,4
4,0,4,4,8,4,0,4,8,4,0,0,4,0,4
0,8,0,4,4,4,4,0,0,0,8,4,4,4,4
4,4,8,4,0,0,4,0,4,4,8,4,0,0,4
4,4,0,8,4,4,0,4,0,0,4,4,0,8,4
0,0,0,0,0,8,8,4,4,4,4,4,4,4,4


All rows (except first) have same freq. distribution of walsh transform coefficients. Hence this sbox has complete linear redundancy. Am i correct ?

Given $S:F_2^n\rightarrow F_2^n$, define the (generalized) walsh transform coefficient as $$\hat{S}(a,b)=\sum_{x\in F_2^n} (-1)^{a \cdot x + b \cdot S(x)}.$$
Looking at your array, $b=0$ which gives $$\hat{S}(a,b)=\sum_{x\in F_2^n} (-1)^{a \cdot x}=0,$$ should result in a zero sum for all $a\neq 0$ and a sum of $2^n=2^4=16$ giving a row or column with 15 $0$s and one $16.$ You have omitted one column, which I shall assume corresponds to $a=0.$
Otherwise, what is observed from your array is that the multiset of absolute values for nontrivial linear selections of the sbox bits ($b\neq 0$),i.e., the multisets $$M_b=\{|\hat{S}(a,b)|: a \in F_2^n\}$$ where we count frequencies of occurence of distinct transform values are invariant with respect to different values of $a,$ which is a kind of uniformity. I wouldn't call it "minimal redundancy" without a definition of what that term might mean. Moreover, due to the absolute value, this is equivalent to the following multisets $$M_b=\{|\hat{S}(a,b)|^2: a \in F_2^n\}$$ begin invariant. In general, from Parseval, we would have $$\sum_{a \in F_2^n}|\hat{S}(a,b)|^2,$$ be a constant, and maybe the maximum redundancy would correspond to these magnitudes all being the same, i.e., $\pm 2^{n/2}$ which could occur only with $n$ even. In any case from Parseval we can deduce that the omitted values in the other rows are $$\sqrt{2^{8}-2\times 8^2-8\times 4^2}=0$$ which could also been directly inferred but this means that your other values are admissible as walsh coefficients so it's useful. But I fail to see why the multiset of values you exhibit (including the missing one) $$\{8(2~times),4(8~times),0(6~times)\}$$ are in some sense minimally redundant, without some kind of result on divisibility properties (by some $2^i$) for walsh coefficients of Sboxes (which I assume are permutations). Such properties are usually deeply algebraic in nature.