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:


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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.