Recently algebraic attack is received a lot of attention in cryptography (Courtois
and Meier, 2002; Dalai et al., 2004a, b;
Lobanov, 2005; Carlet et al.,
2006). A new cryptographic criterion, algebraic immunity is given to resist
this attack. Subsequently the combinations among algebraic immunity and other
requirements to Boolean functions exploited as nonlinear filters in stream ciphers
are studied. More respect was given in the problem of the relations between
algebraic immunity and nonlinearity of Boolean functions.
Dalai et al. (2004a, b)
was proved the lower bound for the nonlinearity of a Boolean function via its
algebraic immunity. The result showed that a Boolean function with low nonlinearity
will have low algebraic immunity. Lobanov (2005) has
shown the stronger tight lower bound for the nonlinearity of a Boolean function
via its algebraic immunity and construct balanced Boolean functions with this
bound for all possible values of parameters.
In this study we give a more general construction of these balanced algebraic immunity Boolean functions that with Lobanovs bound for all possible values of parameters and take the previous construction as an example. Furthermore from the construction it can get a lower bound of the count of balanced algebraic immune functions with Lobanovs bound. As far as we know, this is the first bound about this count.
A Boolean function of n variable is a mapping f: F2n → F2 where F2 is the field of two elements. Any Boolean function has its Algebraic Normal Form (ANF):
where, a0....,ail...ik ∈F2. The algebraic degree of f is the number of variables in the highest order term in the above ANF. The weight wt (x) of a vector x in F2n is the number of ones in x.
Definition 1: If f1 and f2 are Boolean functions of n variable then the distance between f1 and f2 is defined as:
Definition 2: If f is a Boolean function of n variable then the nonlinearity nl (f) of f over F2n is defined as:
Definition 3: If f is a Boolean function of n variable then for any vector u ∈ F2, the Walsh coefficient of f at u is:
The nonlinearity is expressed via Walsh coefficients by the next formula:
Definition 4: For a given n-variable Boolean function f, a nonzero n-variable
Boolean function g is called an annihilator of f if f.g = 0 and the algebraic
immunity of f denoted by AI (f) is the minimum value of d such that f or f+1
admits an annihilating function of degree d. Dalai et al.
(2004a) proved that if:
then Al (f)≤d+1. This is equivalent to the lower bound of nonlinearity:
Lobanov (2005) improved the result.
Lemma 1 (Lobanovs bound). Let f(x1,
,xn) be a Boolean function over F2n and AI(f) = k then:
Definition 5: A boolean function f(x) is called self-dual if f(x1+1,
, xn+1) = f(x1,
It is easy to see that if f is self-dual then the fact that f has not a nonzero annihilator of degree less than k follows that f +1 has not a nonzero annihilator of degree less than k too. Therefore the minimum degrees of nonzero annihilators of functions f and f+1 are the same. Thus, for the finding of algebraic immunity of a self-dual function f it is sufficient to consider only annihilators of the function f.
CONSTRUCTION AND COUNT
Combination foundation: First, an important theorem in combination for the construction was shown.
Lemma 2: For any natural number n and i, 0≤i≤n
Lemma 3: For any natural number n and k, 0≤k<n
Theorem 1: For any natural number n, m and k, 0≤k<n, 0≤m<k-2
Proof, we use the induction to prove the theorem. There is only one induction on m. If m = 0, then the equation is obviously right. If m = 1, then Lemma 3 provides the base case.
Next the induction hypothesis was made that the equation is right for if m, m+1,
So the theorem is proved.
In this subsection, we show the general construction of balanced algebraic immunity Boolean functions with Lobanovs nonliearity bound. The construction is listed below:
Construction: For any n and any,
m is an odd number >n-2k, define the function fn,k by the next way:
If m = 1 then it is Lobanov (2005)s construction
Theorem 2: The functions constructed with the above construction are balanced, Al (fn,k(x1,...,xn) = k and achieve Lobanovs bound. Proof, Note that f (x1+1,...,xn+1) = f (x1+1,...,xn+1), i.e., fn,k is a self-dual function. Hence, the function fn,k is a balanced function.
Since fn,k is self-dual in order to prove Al (fn,k)≥, k, it is sufficient to prove that fn,k+1 has not a nonzero annihilator of degree <k.
Write the possible annihilator g of the function f+1 of degree at most k-1 by means of indeterminate coefficients:
The function g is the annihilator of fn,k+1 if and only if fn,k+1 = 1 follows g (x). We obtain the system of homogeneous linear equations on the coefficients of the functions g: g (x1...,xn) for all vectors x such that wt (x)≤k-1.
Since g (0,...,0) = 0, we have α0 = 0. Since g (x) if wt (x)
= 1, we have ai...a0 = 0. Applying the induction on the
weight of vectors we obtain that all coefficients of g are zeros. Hence, g (x)
= 0. Thus, Al (fn,k)≥k. At the same time it is easy to see that
g (x1...,xn) = (x1+1)...(x1+1) is
the annihilator of fn,k of degree k. Therefore Al (fn,k)
= k,. Calculate the Walsh coefficient of the function fn,k at the
vector (1,0,...,0) using the self-duality offn,k:
Hence, from Lemma 1, it get:
Count: Use the construction for any odd m >n-2k, it can get (n, m) balanced algebraic immune functions with Lobanovs bound, so: a lower bound of the count of these functions. As far as was got, this is the first bound about this count.
Theorem 3: The count of balanced algebraic immune functions with Lobanovs bound satisfied is more than:
In this correspondence, a general construction of balanced algebraic immunity Boolean function was given which has the tight nonlinearity bound proved by Lobanov and firstly gave a bound of these functions. It is interesting to study whether there are other constructions of these algebraic immunity Boolean functions.