Monomial Boolean functions with large high-order nonlinearities

Exhibiting an explicit Boolean function with a large high -order nonlinearity is an important problem in cryptography, coding theory, and computational complexity. We prove lower bounds on the second -order, third -order, and higher order nonlinearities of some monomial Boolean functions. We prove lower bounds on the second -order nonlinearities of functions trn(x7) and trn(x2r+3) where n = 2r. Among all monomial Boolean functions, our bounds match the best second -order nonlinearity lower bounds by Carlet [IEEE Transactions on Information Theory 54(3), 2008] and Yan and Tang [Discrete Mathematics 343(5), 2020] for odd and even n, respectively. We prove a lower bound on the third -order nonlinearity for functions trn(x15), which is the best third -order nonlinearity lower bound. For any r, we prove that the r-th order nonlinearity of trn(x2r+1-1) is at least 2n-1 -2(1-2-r)n+ r 2r-1 -1 - O (2n2 ). For r << log2 n, this is the best lower bound among all explicit functions. (c) 2024 Elsevier Inc. All rights reserved.