On the Lower Bounds of the Second Order Nonlinearity of some Boolean Functions.
Sugata Gangopadhyay, Sumanta Sarkar, Ruchi Telang · IACR Cryptology ePrint Archive · 2009
The r-th order nonlinearity of a Boolean function is an important cryptographic criterion in analyzing the security of stream as well as block ciphers. It is also important in coding theory as it is related to the covering radius of the Reed-Muller code R(r, n). In this paper we deduce the lower bounds of the second order nonlinearity of the following two types of Boolean functions: 1. fλ(x) = Trn 1 (λx d) with d = 22r + 2r + 1 and λ ∈ F2n where n = 6r. 2. f(x, y) = Trt 1(xy 2i+1) where x, y ∈ F2t , n = 2t, n ≥ 6 and i is an integer such that 1 ≤ i < t, gcd(2t − 1, 2i + 1) = 1. For some λ, the functions of the first type are bent functions whereas Boolean functions of the second type are all bent functions, i.e., they possess maximum first order nonlinearity. It is demonstrated that in some cases our bounds are better than the previously obtained bounds.