A Lower Bound on the Second-Order Nonlinearity of the Generalized Maiorana-McFarland Boolean Functions

Qi GAO  Deng TANG  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.12   pp.2397-2401
Publication Date: 2018/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.2397
Type of Manuscript: Special Section LETTER (Special Section on Signal Design and Its Applications in Communications)
Category: Cryptography and Information Security
Keyword: 
Boolean function,  second-order nonlinearity,  bent function,  differential uniformity,  

Full Text: PDF(312KB)
>>Buy this Article


Summary: 
Boolean functions used in stream ciphers and block ciphers should have high second-order nonlinearity to resist several known attacks and some potential attacks which may exist but are not yet efficient and might be improved in the future. The second-order nonlinearity of Boolean functions also plays an important role in coding theory, since its maximal value equals the covering radius of the second-order Reed-Muller code. But it is an extremely hard task to calculate and even to bound the second-order nonlinearity of Boolean functions. In this paper, we present a lower bound on the second-order nonlinearity of the generalized Maiorana-McFarland Boolean functions. As applications of our bound, we provide more simpler and direct proofs for two known lower bounds on the second-order nonlinearity of functions in the class of Maiorana-McFarland bent functions. We also derive a lower bound on the second-order nonlinearity of the functions which were conjectured bent by Canteaut and whose bentness was proved by Leander, by further employing our bound.