Suppose that pS : {0, 1} m ? {0, 1} n is an S-Box. Let the pair (a, b), where a = (a1, . . . , am),.

Suppose that pS : {0, 1} m ? {0, 1} n is an S-Box. Let the pair (a, b), where a = (a1, . . . , am), b = (b1, . . . , bn), ai , bj ? {0, 1} and 1 = i = m; 1 = j = n denote the linear approximation, (Lm i=1 aixi) ? ( Ln j=1 bjyj ) = 0 Let NL(a, b) be an entry in the Linear Approximation Table, that is the number of input and output pairs for the S-Box which satisfy a given approximation (a, b). Prove the following facts about the function NL(a, b): i. NL(0, 0) = 2m ii. NL(a, 0) = 2m – 1 for all integers a such that 0 = a = 2 m – 1 iii. For all integers a such that 0 = a = 2 m – 1, it holds that: 2 Xm-1 a=0 NL(a, b) = 22m-1 ± 2 m-1