Highly Nonlinear Boolean Functions with Optimal Algebraic Immunity and  Good Behavior Against Fast Algebraic Attacks

Deng Tang; Claude Carlet; Xiaohu Tang

Paper 2011/366

Highly Nonlinear Boolean Functions with Optimal Algebraic Immunity and Good Behavior Against Fast Algebraic Attacks

Deng Tang, Claude Carlet, and Xiaohu Tang

Abstract

In this paper, we present a new combinatorial conjecture about binary strings. Based on the new conjecture, two classes of Boolean functions of $2 k$ variables with optimal algebraic immunity are proposed, where $k \geq 2$ . The first class contains unbalanced functions having high algebraic degree and nonlinearity. The functions in the second one are balanced and have maximal algebraic degree and high nonlinearity. It is checked that, at least for small numbers of variables, both classes of functions have a good behavior against fast algebraic attacks. Compared with the known Boolean functions resisting algebraic attacks and fast algebraic attacks, the two classes of functions possess the highest lower bounds on nonlinearity. These bounds are however not enough for ensuring a sufficient nonlinearity for allowing resistance to the fast correlation attack. Nevertheless, as for previously found functions with the same features, there is a gap between the bound that we can prove and the actual values computed for small numbers of variables. Moreover, these values are very good and much better than for the previously found functions having all the necessary features for being used in the filter model of pseudo-random generators.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.
Keywords: Boolean functions balancedness algebraic immunity fast algebraic attack algebraic degree nonlinearity.
Contact author(s): dengtanghome @ qq com
History: 2011-07-10: received
Short URL: https://ia.cr/2011/366
License: CC BY

BibTeX

@misc{cryptoeprint:2011/366,
      author = {Deng Tang and Claude Carlet and Xiaohu Tang},
      title = {Highly Nonlinear Boolean Functions with Optimal Algebraic Immunity and  Good Behavior Against Fast Algebraic Attacks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/366},
      year = {2011},
      url = {https://eprint.iacr.org/2011/366}
}