The Nonlinearity Lower Bounds on the Second Order of Cubic Monomial Boolean Functions

This paper investigates cubic monomial Boolean functions f_μ(x)=Tr(μx^d) with n variables, where d=2ⁱ+2^j+1,μ∈GF(2ⁿ)^*, and n＞i＞j. The known results show that the Boolean functions f_μ(x) has good lower bounds on the second nonlinearity for n＞2i. This paper firstly studies all lower bounds on the nonlinearity of the derivatives of f_μ(x), then the lower bounds on the second order nonlinearity of f_μ(x) for n≤2i are given. The results show that the lower bounds on the second order nonlinearity of f_μ(x) for n≤2i are tighter than that of f_μ(x) for n＞2i. Therefore, whether n＞2i or n≤2i, the Boolean functions f_μ(x) can resist quadratic or linear approximation attacks.