Abstract: Recently Lobanov’s tight bound of nonlinearity of balanced algebraic immune Boolean functions has received a lot of attention in cryptographic literature. In this study a general construction of balanced algebraic immune Boolean functions was given with the nonlinearity bound. Moreover from the construction, we get a lower bound of the count of balanced algebraic immune functions was got with the nonlinearity bound. As far as we know, this is the first bound about this count.

INTRODUCTION

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 Lobanov’s 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 Lobanov’s bound. As far as we know, this is the first bound about this count.

PRELIMINARIES

A Boolean function of n variable is a mapping f: F₂ⁿ → F₂ where F₂ is the field of two elements. Any Boolean function has its Algebraic Normal Form (ANF):

where, a₀....,a_il..._ik ∈F₂. 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 F₂ⁿ is the number of ones in x.

Definition 1: If f₁ and f₂ are Boolean functions of n variable then the distance between f₁ and f₂ is defined as:

Definition 2: If f is a Boolean function of n variable then the nonlinearity nl (f) of f over F₂ⁿ is defined as:

Definition 3: If f is a Boolean function of n variable then for any vector u ∈ F₂, 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 (Lobanov’s bound). Let f(x₁,…,x_n) be a Boolean function over F₂ⁿ and AI(f) = k then:

Definition 5: A boolean function f(x) is called self-dual if f(x₁+1,…, x_n+1) = f(x₁, …, x_n)+1.

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

Proof,

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.

CONSTRUCTION

In this subsection, we show the general construction of balanced algebraic immunity Boolean functions with Lobanov’s nonliearity bound. The construction is listed below:

Construction: For any n and any,

m is an odd number >n-2k, define the function f_n,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 (f_n,k(x₁,...,x_n) = k and achieve Lobanov’s bound. Proof, Note that f (x₁+1,...,x_n+1) = f (x₁+1,...,x_n+1), i.e., f_n,k is a self-dual function. Hence, the function f_n,k is a balanced function.

Since f_n,k is self-dual in order to prove Al (f_n,k)≥, k, it is sufficient to prove that f_n,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 f_n,k+1 if and only if f_n,k+1 = 1 follows g (x). We obtain the system of homogeneous linear equations on the coefficients of the functions g: g (x₁...,x_n) for all vectors x such that wt (x)≤k-1.

Since g (0,...,0) = 0, we have α₀ = 0. Since g (x) if wt (x) = 1, we have a_i...a₀ = 0. Applying the induction on the weight of vectors we obtain that all coefficients of g are zeros. Hence, g (x) = 0. Thus, Al (f_n,k)≥k. At the same time it is easy to see that g (x₁...,x_n) = (x₁+1)...(x₁+1) is the annihilator of f_n,k of degree k. Therefore Al (f_n,k) = k,. Calculate the Walsh coefficient of the function f_n,k at the vector (1,0,...,0) using the self-duality off_n,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 Lobanov’s 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 Lobanov’s bound satisfied is more than:

CONCLUSION

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.