Improving the Lower Bound on the Higher Order Nonlinearity of Boolean Functions With Prescribed Algebraic Immunity
Sihem Mesnager · IEEE Transactions on Information Theory · 2008
The recent algebraic attacks have received a lot of attention in cryptographic literature. The algebraic immunity of a Boolean function quantifies its resistance to the standard algebraic attacks of the pseudorandom generators using it as a nonlinear filtering or combining function. Very few results have been found concerning its relation with the other cryptographic parameters or with therth-order nonlinearity. As recalled by Carlet at CRYPTO'06, many papers have illustrated the importance of therth-order nonlinearity profile (which includes the first-order nonlinearity). The role of this parameter relatively to the currently known attacks has been also shown for block ciphers. Recently, two lower bounds involving the algebraic immunity on therth-order nonlinearity have been shown by Carlet . None of them improves upon the other one in all situations. In this paper, we prove a new lower bound on therth-order nonlinearity profile of Boolean functions, given their algebraic immunity, that improves significantly upon one of these lower bounds for all orders and upon the other one for low orders.