## IACR paper details

Title | Algebraic Immunity Hierarchy of Boolean Functions |
---|

Booktitle | IACR Eprint archive |
---|

Pages | |
---|

Year | 2007 |
---|

URL | http://eprint.iacr.org/2007/259 |
---|

Author | Ziran Tu |
---|

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

Search for the paper

@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
}

Download a complete BibTeX file.