International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Xiaohu Tang
Deng Tang
Xiangyong Zeng
Lei Hu
Download:
URL: http://eprint.iacr.org/2010/443
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2010-23344,
  title={Balanced Boolean Functions with (Almost) Optimal Algebraic Immunity and Very High Nonlinearity},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / boolean functions},
  url={http://eprint.iacr.org/2010/443},
  note={ xhutang@vip.sina.com 14836 received 15 Aug 2010},
  author={Xiaohu Tang and Deng Tang and Xiangyong Zeng and Lei Hu},
  year=2010
}