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 tr n ( x 7 ) and tr n ( x 2 r + 3 ) where n = 2 r. 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 tr n ( x 15 ), which is the best third-order nonlinearity lower bound. For any r, we prove that the r-th order nonlinearity of tr n ( x 2 r + 1 − 1 ) is at least 2 n − 1 − 2 ( 1 − 2 − r ) n + r 2 r − 1 − 1 − O ( 2 n 2 ). For r ≪ log 2 ⁡ n, this is the best lower bound among all explicit functions.

Authors

• Jinjie Gao
• Haibin Kan
• Yuan Li
• Jiahua Xu
• Qichun Wang

Keywords

• High-order nonlinearity
• Monomial Boolean function
• Lower bound
• Trace function
• Linear kernel