**Algebraic Immunity Hierarchy of Boolean Functions**

*Ziran Tu and Yingpu Deng*

**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.

**Category / Keywords: **foundations / Boolean functions; algebraic attack; algebraic immunity;nonlinearity; stream cipher

**Date: **received 1 Jul 2007

**Contact author: **dengyp at amss ac cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20070703:072213 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]