International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Algebraic Immunity Hierarchy of Boolean Functions

Authors:
Ziran Tu
Yingpu Deng
Download:
URL: http://eprint.iacr.org/2007/259
Search ePrint
Search Google
Abstract: Algebraic immunity of Boolean functions is a very important concept in recently introduced algebraic attacks of stream cipher. For a $n$-variable Boolean function $f$, the algebraic immunity $AI_n(f)$ takes values in $\{0,1,\ldots,\lceil\frac{n}{2}\rceil\}$. For every $k$ in this range, denote $B_{n,k}$ the set of all $n$-variable Boolean functions with algebraic immunity $k$, and we know that $B_{n,k}$ is always non-empty. According to the algebraic immunity, we can form a hierarchy of Boolean functions. Trivially, $|B_{n,0}|=2$. In general, about this integer sequence $|B_{n,k}|,\quad k=0,1,\ldots,\lceil\frac{n}{2}\rceil,$ very few results are known. In this paper, we show an explicit formula for $|B_{n,1}|$. That is, we obtain an exact formula for the number of Boolean functions with algebraic immunity one. This is the first exact formula for the terms in the above integer sequence. We also give a tight upper bound for nonlinearity of Boolean functions with algebraic immunity one.
BibTeX
@misc{eprint-2007-13540,
  title={Algebraic Immunity Hierarchy of Boolean Functions},
  booktitle={IACR Eprint archive},
  keywords={foundations / Boolean functions; algebraic attack; algebraic immunity;nonlinearity; stream cipher},
  url={http://eprint.iacr.org/2007/259},
  note={ dengyp@amss.ac.cn 13696 received 1 Jul 2007},
  author={Ziran Tu and Yingpu Deng},
  year=2007
}