Consider the Boolean fuctions f(x) : {0, 1} m ? {0, 1} and g(y) : {0, 1} n ? {0, 1}. Assume f and g

Consider the Boolean fuctions f(x) : {0, 1} m ? {0, 1} and g(y) : {0, 1} n ? {0, 1}. Assume f and g operates on statistically independent variables. Denote Wf (w) = Px (-1)f(x)?x.w, where w ? {0, 1} m. Answer the following questions: i. Prove that if f is balanced Wf (0) = 0. ii. Prove that if f is a balanced function then f(x) ? g(y) is always balanced. iii. If the non-linearity of f is denoted by Nf , then prove that Nf = 2n-1 – 1 2 |Wmax|, where |Wmax| is the maximum absolute value among all the Wf (w), ?w. iv. A Boolean function f in n variables is called bent if and only if the values of Wf (w), ?w are all ±2 n/2 . Prove that the Boolean function f(x) ? g(y) is bent if f and g are bent functions. v. Using the above results prove that the Boolean function x1x2 ? x3x4 ? x5x6 ? . . . ? xn-1xn is a bent Boolean function.