LOWER BOUNDS ON THE SECOND ORDER NONLINEARITY OF BOOLEAN FUNCTIONS
It is a difficult task to compute the r-th order nonlinearity of a given function with algebraic degree strictly greater than r > 1. Though lower bounds on the second order nonlinearity are known only for a few particular functions, the majority of which are cubic. We investigate lower bounds on the second order nonlinearity of cubic Boolean functions F(x) = Tr(Sigma(m)(l=1)mu(l)x(dl)), where mu(l) is an element of F*(2n), d(l) = 2(il) + 2(jl) + 1, m, i(l) and j(l) are positive integers, n > i(l) > j(l). Furthermore, for a class of Boolean functions G(x) = Tr(Sigma(m)(l=1)mu(l)x(dl)), we deduce a tighter lower bound on the second order nonlinearity of the functions, where mu(l) is an element of F*(2n), d(l) = 2(il gamma) + 2(jl gamma) + 1, i(l) > j(l) and gamma not equal 1 is a positive integer such that gcd(n, gamma) = 1. Lower bounds on the second order nonlinearity of cubic monomial Boolean functions, represented by f(mu)(x) = Tr(mu x(2i+2j+1)), mu is an element of F*(2n), i and j are positive integers such that i > j, were obtained by Gode and Gangopadhvay in 2009. In this paper, we first extend the results of Gode and Gangopadhvay from monomial Boolean functions to Boolean functions with more trace terms. We further generalize and improve the results to a wider range of n. Our bounds are better than those of Gode and Gangopadhvay for monomial functions f(mu)(x). Especially, our lower bounds on the second order nonlinearity of some Boolean functions F(x) are better than the existing ones.
nonlinearity boolean functions cryptography walsh transform derivation