Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity

Sihem Mesnager

Paper 2007/117

Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity

Sihem Mesnager

Abstract

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 pseudo-random 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 the $r$-th order nonlinearity. As recalled by Carlet at Crypto'06, many papers have illustrated the importance of the $r$th-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 the $r$th-order nonlinearity have been shown by Carlet et \emph{al}. None of them improves upon the other one in all situations. In this paper, we prove a new lower bound on the $r$th-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.

Note: I have made several (and important) modifications of my paper that improves the overall presentation. I would like that this version replace the one that I have put on your website. Sincerely yours,

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Keywords: stream cipher block cipher algebraic attack Boolean function algebraic immunity algebraic degree higher order nonlinearity annihilator
Contact author(s): hachai @ math jussieu fr
History: 2007-08-03: revised; 2007-04-03: received; See all versions
Short URL: https://ia.cr/2007/117
License: CC BY

BibTeX

@misc{cryptoeprint:2007/117,
      author = {Sihem Mesnager},
      title = {Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/117},
      year = {2007},
      url = {https://eprint.iacr.org/2007/117}
}