Welcome to the resource topic for 2007/259
Title:
Algebraic Immunity Hierarchy of Boolean Functions
Authors: Ziran Tu, 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.
ePrint: https://eprint.iacr.org/2007/259
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .