Balanced Boolean Functions with (Almost) Optimal Algebraic Immunity and Very High Nonlinearity

Xiaohu Tang; Deng Tang; Xiangyong Zeng; Lei Hu

Paper 2010/443

Balanced Boolean Functions with (Almost) Optimal Algebraic Immunity and Very High Nonlinearity

Xiaohu Tang, Deng Tang, Xiangyong Zeng, and Lei Hu

Abstract

In this paper, we present a class of $2k$-variable balanced Boolean functions and a class of $2k$-variable $1$-resilient Boolean functions for an integer $k\ge 2$, which both have the maximal algebraic degree and very high nonlinearity. Based on a newly proposed conjecture by Tu and Deng, it is shown that the proposed balanced Boolean functions have optimal algebraic immunity and the $1$-resilient Boolean functions have almost optimal algebraic immunity. Among all the known results of balanced Boolean functions and $1$-resilient Boolean functions, our new functions possess the highest nonlinearity. Based on the fact that the conjecture has been verified for all $k\le 29$ by computer, at least we have constructed a class of balanced Boolean functions and a class of $1$-resilient Boolean functions with the even number of variables $\le 58$, which are cryptographically optimal or almost optimal in terms of balancedness, algebraic degree, nonlinearity, and algebraic immunity.

Metadata

Available format(s): PDF PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: boolean functions
Contact author(s): xhutang @ vip sina com
History: 2010-08-18: received
Short URL: https://ia.cr/2010/443
License: CC BY

BibTeX

@misc{cryptoeprint:2010/443,
      author = {Xiaohu Tang and Deng Tang and Xiangyong Zeng and Lei Hu},
      title = {Balanced Boolean Functions with (Almost) Optimal Algebraic Immunity and Very High Nonlinearity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/443},
      year = {2010},
      url = {https://eprint.iacr.org/2010/443}
}