On Third-Order Nonlinearity of Biquadratic Monomial Boolean Functions

Abstract EN

The rth-order nonlinearity of Boolean function plays a central role against several known attacks on stream and block ciphers.

Because of the fact that its maximum equals the covering radius of the rth-order Reed-Muller code, it also plays an important role in coding theory.

The computation of exact value or high lower bound on the rth-order nonlinearity of a Boolean function is very complicated problem, especially when r>1.

This paper is concerned with the computation of the lower bounds for third-order nonlinearities of two classes of Boolean functions of the form Tr1nλxd for all x∈?2n, λ∈?2n*, where a d=2i+2j+2k+1, where i, j, and   k are integers such that i>j>k≥1 and n>2i, and b d=23ℓ+22ℓ+2ℓ+1, where ℓ is a positive integer such that gcdℓ,?=1 and n>6.