Paper 2007/259

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Boolean functionsalgebraic attackalgebraic immunitynonlinearitystream cipher
Contact author(s)
dengyp @ amss ac cn
History
2007-07-03: received
Short URL
https://ia.cr/2007/259
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/259,
      author = {Ziran Tu and Yingpu Deng},
      title = {Algebraic Immunity Hierarchy of Boolean Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2007/259},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/259}},
      url = {https://eprint.iacr.org/2007/259}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.