Observations Concerning the probability of the existence of annihilators for balanced boolean functions

LFSR-based stream ciphers with nonlinear filters or combiners are susceptible to algebraic attacks using linearization methods to solve an overdefined system of nonlinear equations. And this process is greatly enhanced if the filtering or combining function has a low degree annihilator. To prevent such an attack, one would choose the parameters of that function so that the degree of its annihilator becomes large enough. As computing power is continuously increasing, a choice that seems secure today, becomes insecure tomorrow. Therefore, a tool is needed to estimate the probability of the existence of annihilators for balanced boolean functions with parameters that are beyond the current computing power. Based on experimental and calculational observations, we give in this paper an almost exact estimate of that probability, which represent a great improvement over the upper bound previously known.


Introduction
LFSR stream ciphers with combining nonlinear functions are very efficient in terms of their speed of generating the keystream and their ability to mathematical analysis with respect of controlling the period of their generated sequences. Although these ciphers are nonlinear, they are not immune against algebraic attacks. Indeed, there exists efficient algorithms for linearization and solving nonlinear sets of equations [6], when the degree of the combining function, which is ultimately determined by the number of its inputs, is not too large. Moreover, there also exist algorithms that can find low degree annihilators of such functions so that they can be used to simplify the linearization process, and consequently, recover the encryption key [1,5]. To escape such an attack, one would increase n, the number of the inputs to the combining function, which leads to a larger degree d of its annihilators, and therefore increases its algebraic immunity. The question now is how big n and d should be in order to have a secure system. Using the annihilator's finding algorithms, one can check whether a given combining function has an annihilator, but this process is not sufficient to make a concrete decision about the security of a system. A choice of n and d, that is secure today according to the mentioned checking process, will be insecure tomorrow due to the increasingly growing computing power. And choosing large number of inputs to combining function arbitrarily is not practical. True, the prices of bits are decreasing fast, but there are practical limits that can not be exceeded, especially because the memory requirements of the system grow exponentially with that number. In [5], an upper bound of the probability of the existence of balanced boolean functions annihilators has been derived, so one can predict at what range that number should be. Although that upper bound is good for practical purposes, it suffers from a fatal drawback. In fact, the value of the bound is very overestimated, giving probability values "greater" than 1 for certain values of n an d. And in [2], a better upper bound is derived. In what follows, we present an almost exact formula for the probability of the existence of annihilators of a combining nonlinear boolean function, based on some empirical and calculational observations, but without a regirous mathematical proof. Our interest here is focused on balanced boolean functions, because balanced functions are a requirement in cipher systems.
The paper is organized as follows. In section 2 some definitions are given. In section 3, the algorithms of finding annihilators are quoted from [5]. In section 4, some experimental observations concerning the behavior of annihilators are described. Finally, in section 5, an analysis of the probability of the existence of annihilators for balanced boolean functions is made, following the approach of [5].

Definitions
We present some definitions that are necessary for the rest of the paper.
be a boolean function of n inputs. We call

Finding the annihilators of f
. A necessary and sufficient condition for g to be an annihilator of f, i.e. for 0   g f , is that g vanishes for all arguments x for which 1 ) ( . This leads to the following algorithm: Algorithm 1 (quoted from [5]): Of course, the number of unknowns in this system of linear equations is the number of the coefficients in the ANF of g, which equals s. Since we are interested here in balanced functions only, the number of equations that we can form, i.e. the value of N , will be 1 2  n . Note that this system of linear equations is Algorithm 1 is the basic algorithm for finding the annihilators of a boolean functions f . In [5], there is another, more computationally efficient algorithm, but in essence, it is the same as algorithm 1, although it may sometimes give wrong results.
Algorithm 2 (quoted from [5]): Note that if algorithm 2 is used to find an annihilator of a balanced function f, then all the 1 2  n equations must be involved in the process of solving the system. If one takes, for example, only m equations such that , then the result will be for a function f whose weight is m, not 1 2  n . But there is nothing in algorithm 2 that ensures that it takes all those 1 2  n equations into account. The double checking process of the solutions may partially compensate for that, but it is not sufficient on its own unless 0

Empirical Observations
In [5], an upper bound is given for the probability of the existence of annihilators for balanced boolean functions by theorem 4. This upper bound suffers from being overestimated, and worse, it gives in certain cases probability values "greater" than 1, whereas it is much less than 1, e.g. when 10  n and 4  d [5].
Searching for annihilators for 4 and 10   d n , by repetitively choosing random balanced functions f and applying algorithm 1, shows that this probability must be very small. Therefore there must be something wrong in theorem 4 of [5].
During the search for annihilators, the following observations have been made: , it was noticed that the weights of the annihilators equal, almost always, the minimum weight d n 2 , and very rarely, as shown in Fig. 1. Table 1 shows the curves parameters.
As can be seen from Fig. 1 Fig. 2 for all pairs of n and d listed in table 1. As can be seen from Fig. 2, the average rank r approaches the number of unknowns s minus 1 as the weight of f increases towards 1 2  n , which suggests that a balanced boolean function f admits only one annihilator if its degree .

For n odd and
, we found that many annihilators of different weights annihilate balanced boolean functions f. ) (

The probability of the existence of annihilators for random balanced boolean functions f of n variables
Before proceeding with the discussion of the probability, it is worth mentioning that algorithm 1 leads to the following two lemmas.
It should be clear that f N is the number of balanced functions f admitting an annihilator g of weight    reveals that its terms decrease very rapidly with increasing w. This fact, together with observation 1, leads us to conjecture again that the terms of 3  are also vanishingly negligible, making 1  , i.e. the first term of equation (2), the dominant one. This allows by all means expressing the final result that gives the probability of the existence of an annihilator g of degree d for a balanced function f with n inputs, when , in the following form with a very good accuracy:     1 2   n s , i.e. the number of available equations for algorithm 1 is equal to the number of unknowns. But by lemma 1 and lemma 2, these equations are not necessarily all linearly independent, and therefore the possibility of there being some non trivial solutions exists. On the other hand, removing just one equation from these equations leads always to non trivial solutions, i.e. the system of equations is on the verge of avalanche. This suggests that the probability of the existence of annihilators must be high.
According to observation 3, the annihilators can have many different weights whose enumerators are unknown, and therefore no further concrete statement can be made about the probability of annihilators. However, experiments suggest that:  Table 6 5.3 n even and 2 n d  By corollary 1-d, 1 2   n s , i.e. the number of available equations is less than the number of unknowns. This makes the system of linear equations in algorithm 1 underdefined, and therefore there is always non trivial solutions, giving: