Improving bounds on probabilistic affine tests to estimate the nonlinearity of Boolean functions

Boolean functions are defined on a vector space over the binary finite field \(\mathbb {F}_{2}\) with output in \(\mathbb {F}_{2}\). For many cryptographic applications it is important that functions are not affine, and not even close (with respect to the Hamming distance, defined in (3)) to being affine. The nonlinearity of a function f, denoted \({\mathrm {d}_{\mathcal {A}}}(f)\), defined as the minimum Hamming distance to any affine function, is therefore an important cryptographic property. This indicator can be computed by using the Walsh transform (also called Walsh-Hadamard or discrete Fourier transform). The Walsh transform of a function f in n variables can be computed from its truth table by an algorithm similar to the fast Fourier transform in time O(n2ⁿ). Computing the Walsh transform is not feasible in practice when the number of variables is large (e.g., it is not feasible for functions in 80 variables; functions which model an output of a stream or block cipher as a function of the key would have a number of variables equal to the length of the key, i.e. at least 80 variables) and the function is given as a “black box” (or given by an algorithm or formula which is not amenable to simple manipulation for the purpose of computing the Walsh transform).

The motivation of this paper is to probabilistically estimate the nonlinearity of f to a reasonable degree of accuracy. The main idea is as follows. Consider a probabilistic test (we will see some examples shortly) which has a success/fail outcome based on the values of f at some fixed number k of points in \({\mathbb {F}_{2}^{n}}\) (f can therefore be given as a “black box” function). Denote by T(f) the probability of failing the test (with the probability taken over all possible choices of k inputs in \({\mathbb {F}_{2}^{n}}\)). We assume T(f) is positively correlated, to some extent, with the nonlinearity \(\mathrm {d}_{\mathcal {A}}(f)\), and can be bounded by some functions in \(\mathrm {d}_{\mathcal {A}}(f)\), say \( \text {Lower}(\mathrm {d}_{\mathcal {A}}(f)) \le T(f) \le \text {Upper}(\mathrm {d}_{\mathcal {A}}(f)). \) If we can obtain T(f) with reasonable accuracy by practical statistical testing (e.g. binomial proportion confidence interval), we can then estimate the nonlinearity as: (we use F^− 1(x) to denote the preimage of x under F), or, if the preimage has only one element, To obtain an accurate estimate, it is important that T(f) depend strongly on \(\mathrm {d}_{\mathcal {A}}(f)\) and that the bounds are very good. We will examine several probabilistic tests, improve some of the existing bounds, and analyze the accuracy of the resulting estimation.

The linearity test most commonly used is based on the textbook definition of a linear function, namely f(u + v) = f(u) + f(v) (often called the BLR test from [3]): what it means is that we pick \(u,v{\in \mathbb {F}_{2}^{n}}\) uniformly at random, compute u + v, query the black box to extract f(u),f(v),f(u + v), and check if the aforementioned condition holds. If f passes this test for many pairs (u,v), then f is probably linear. If f fails the test for at least one pair, then f is certainly not linear. We denote by P₂(f) the probability of f failing the test (with probability taken over all pairs \((u, v)\in {\mathbb {F}_{2}^{n}}{\times \mathbb {F}_{2}^{n}}\)) and by \(\mathrm {d}_{{\mathscr{L}}}(f)\) the normalized Hamming distance of f to the closest linear function. Several authors have determined upper and lower bounds for P₂(f) as a function of \(\mathrm {d}_{{\mathscr{L}}}(f)\) (see [1, 9] and the references therein).

For cryptographic applications we are not so much interested in whether the function is linear, but rather whether it is affine. For example, such tests play a crucial role in the cube and AIDA attacks (see [6, 12]), which are refined high-order differential attacks, targeted at primitives in stream and block ciphers based on low-degree components. The probabilistic test used in [6] for deciding whether a function f is affine is to check whether f(u + w) + f(u) + f(w) + f(0) = 0 holds (for u,w chosen uniformly at random), which can be viewed as using the BLR test to check whether f(u) − f(0) is linear. The functions of interest f are functions in many variables (typically at least 80 variables), obtained as higher-order derivatives of a function g which describes, for example, the first output bit of the stream cipher as a function of the key and initialisation vector. Although explicit algorithms are available for computing g and f (in the case of the Trivium cipher, the algorithm for computing g starts with some relatively simple functions of algebraic degree two, which are iteratively composed 1152 times for the full cipher, or about 700 times for reduced versions of the cipher), it is not feasible in practice to compute their algebraic normal form, or truth table, or nonlinearity, or Walsh transform. Instead, g is treated as a “black box” function, and f can be evaluated at any given input using several calls to g.

Another test used in the literature for deciding whether a Boolean function is affine is to check whether the equation f(u + v + w) + f(u) + f(v) + f(w) = 0 holds, for some \(u,v,w\in {\mathbb {F}_{2}^{n}}\) chosen uniformly at random. Like in the case of the linearity test, if f passes the test for many triples u,v,w, then f is probably affine. We denote by P₃(f) the probability of f failing this affinity test (with the probability taken over all triples \((u, v, w)\in \mathbb {F}_{2}^{3n}\)). As in the case of the linearity tests, a natural question is whether P₃(f) is related to \(\mathrm {d}_{\mathcal {A}}(f)\), the distance to the closest affine function (note that this is the nonlinearity of f ). A lower bound for P₃(f) in terms of \(\mathrm {d}_{\mathcal {A}}(f)\) was given in Bellare et al. [1].

A generalization of the tests above was proposed by Zhang and Zheng in [14], where the authors defined the notion of (k + 1)-st order nonhomomorphicity of a function f as the probability P_k(f) of failing the test with the probability taken over all tuples \((u_{1}, \ldots , u_{k})\in ({\mathbb {F}_{2}^{n}})^{k}\) (see Definition 1). It was shown that for k odd, f is affine if and only if P_k(f) = 0; for k even, f is linear if and only if P_k(f) = 0; also, still for k even, f is affine if and only if P_k(f) ∈{0,1}. Furthermore, some bounds on P_k(f) with respect to \(\mathrm {d}_{\mathcal {A}}(f)\), for k odd, were given in [14].

In this paper, we firstly improve both the upper and lower bounds presented by Zhang and Zheng in [14] for P_k(f) with k odd (see Sections 3 and 4). Our lower bound holds for arbitrary k and generalizes the lower bound proven in [1] for k = 2,3. The proofs use the techniques employed in [1] as well as additional combinatorial manipulation. We also prove the lower bound we conjectured in [11].

Secondly, we consider the following probabilistic test for affine functions. We can use any probabilistic linearity test, and test whether f is linear or f + 1 is linear. If either of these holds, then f is affine. For the nonhomomorphicity test with k even, this is equivalent to testing whether P_k(f) ∈{0,1}. The fact that f is affine if and only if P_k(f) ∈{0,1} was proven in [14]. However, when f is not affine no results were given regarding how the probability of failing this test depends on the nonlinearity of f. In Section 5 we show that upper and lower bounds can be obtained for the value of \(\min \limits (P_{k}(f), P_{k}(f+1))\) in the case k = 2 (i.e. the BLR test). Namely, using the bounds on failing the BLR linearity test from [1], which depend on the distance to the closest linear function, we show that similar bounds hold for \(\min \limits (P_{2}(f), P_{2}(f+1))\), but this time the bounds depend on the distance to the closest affine function. We also show that the refinements of the bounds from [1] given in [9] can be applied to our bounds too.

The nonlinearity of a function f can be estimated by first using any of the above tests and a practical statistical method to estimate the probability of failing that test (as demonstrated in [14]). Then, using (1) or (2), we obtain an estimate for the nonlinearity of f. In Section 6 we analyze the accuracy of the estimation. There are functions f,g such that f has higher probability of failing the test than g, even though f has lower nonlinearity than g. This was shown in [2] for the BLR test and in [14] for the tests based on the (k + 1)-st order nonhomomorphicity with k odd. However, the estimates get more accurate as k increases. For example, for k = 7, for any given value of P₇(f) we can estimate the nonlinearity as being within an interval of length 0.011 or less if P₇(f) ≤ 0.49 and length 0.053 or less if P₇(f) ∈ [0.49,0.5].

Other nonlinearity tests were proposed for reducing the number of evaluations needed for the black box function, such as [7, 13] (the latter being also useful to estimate the algebraic degree of f ). The (k + 1)-st order nonhomomorphicity for k = 3 was used for attacks on actual ciphers in [10]. We intend to push further the connection between the probability of failing these tests and the nonlinearity, as well as look at estimating the nonlinearity of functions of cryptographic interest.

We recall definitions and known results needed for the rest of the paper.

Throughout, n will denote a positive integer. Boolean functions in n variables are functions \(f :{\mathbb {F}_{2}^{n}} \rightarrow \mathbb {F}_{2}\), where \(\mathbb {F}_{2}\) is the binary field, and \({\mathbb {F}_{2}^{n}}\) is the n dimensional vector space over \(\mathbb {F}_{2}\). It is well known that any such function can be uniquely represented in its ANF (Algebraic Normal Form), i.e. as a polynomial in \(\mathbb {F}_{2}[x_{1}, \ldots , x_{n}]\) of degree at most 1 in each variable. The total degree of the ANF representation is called the algebraic degree of f. Functions of algebraic degree at most one are called affine; affine functions with zero constant term are called linear. We will denote by \(\mathcal {A}\) the set of affine functions and by \({\mathscr{L}}\) the set of linear functions in n variables over \(\mathbb {F}_{2}\), if the dimension is understood from the context.

In this paper, like in [1], it will be convenient to use the normalized version of the Hamming distance and weight. More precisely, we define the (normalized) Hamming distance and Hamming weight for vectors a = (a₁,…,a_t) and b = (b₁,…,b_t) in \({\mathbb {F}_{2}^{t}}\), as well as the distance of a vector \(a\in {\mathbb {F}_{2}^{t}}\) to a set of vectors \(S\subseteq {\mathbb {F}_{2}^{t}}\) as: In the literature, the Hamming weight and distance are more often used without normalization (i.e. in the definitions above, one does not divide by the length of the vector) but we will explain shortly why normalization is useful for our purpose. The truth table of a function f is the vector \(TT(f)=(f(v_{0}), \ldots , f(v_{2^{n}-1}))\), where v_i are all the elements of \({\mathbb {F}_{2}^{n}}\) in some fixed order, e.g., lexicographical order. The (normalized) Hamming weight, denoted by w(f), of a Boolean function f is w(TT(f)) and the distance, denoted by d(f,g), between two Boolean functions f,g is d(TT(f),TT(g)).

Of particular importance will be the distance of a function f to the set of affine or of linear functions. The minimum distance to any affine function, \(\mathrm {d}_{\mathcal {A}}(f)\), is called the (normalized) nonlinearity of f and is a very important cryptographic indicator. It is easy to see that \(\mathrm {d}_{\mathcal {A}}(f) = \min \limits (\mathrm {d}_{{\mathscr{L}}}(f), \mathrm {d}_{{\mathscr{L}}}(f+1))\). Our motivation for using the normalized version of nonlinearity (based on the normalized version of Hamming distance) is that it allows a meaningful comparison of the nonlinearity of two functions which might not have the same number of variables.

The Fourier-Hadamard transform of a function \(f:{\mathbb {F}_{2}^{n}} \rightarrow \mathbb {R}\) (the 0/1 values of a Boolean functions are viewed as real numbers for this purpose) is the function \(W(f): {\mathbb {F}_{2}^{n}} \rightarrow \mathbb {R}\) defined as where the dot product can be defined as \(u \cdot v = {\sum }_{i=1}^{n}u_{i}v_{i}\). Note that we use a normalized version of the transform here. If f is replaced by its sign function, \(\hat f\), defined by \(\hat f(u)=(-1)^{f(u)}\), then \(W(\hat f)\) is customarily referred to as the Walsh (or Walsh-Hadamard) transform of f, and the values \(W(\hat f)(v)\) for \(v\in {\mathbb {F}_{2}^{n}}\) are called the Walsh coefficients. We will refer to the sequence of output values of the Walsh transform (when the input is ordered lexicographically) as the Walsh spectrum.

We will be using later Parseval’s identity (see [5] for example): which holds for any Boolean function f.

It is well-known [5] and easy to see that the Walsh transform of a Boolean function f expresses its distance to the set of linear functions, and consequently the distance of f to the set of affine functions. Denoting ℓ_a(u) = a ⋅ u, the nonlinearity of f is related to the Walsh transform as follows: Note that \(0\le \mathrm {d}_{{\mathscr{L}}}(f) \le \frac {1}{2}\). It is known [5] that \(0\le \mathrm {d}_{\mathcal {A}}(f) \le \frac {1}{2}\left (1 - \frac {1}{2^{\frac {n}{2}}}\right )\). We call a function \(f:{\mathbb {F}_{2}^{n}}\to \mathbb {F}_{2}\) (n ≥ 2) bent if its nonlinearity is exactly \(\frac {1}{2}\left (1 - \frac {1}{2^{\frac {n}{2}}}\right )\) (they exist only for even integers n). It is known [5] that f is bent if and only if the absolute values of all of its Walsh coefficients satisfy \(|W(\hat f)(v)|=2^{-\frac {n}{2}}\).

We consider the test of whether a function is affine by checking whether f(u₁ + ⋯ + u_k) + f(u₁) + ⋯ + f(u_k) = 0, for some fixed odd integer k. We examine the relationship between the probability P_k(f) of failing this test and \(\mathrm {d}_{\mathcal {A}}(f)\), the nonlinearity of f. It is well known, and easy to prove, that f is affine if and only if P_k(f) = 0.

A lower bound for P₃(f) was proven in [1, Lemma 5.1] (with \(x = \mathrm {d}_{\mathcal {A}}(f)\)):

The following lower and upper bounds were given in [14] for k odd (we reformulated them to use the normalized version):

We improve on the bounds (7) as follows:

Note that for k ≥ 3 odd, the bounds in the theorem above are better than the bounds (7). The lower bound in (7) is negative when \(\mathrm {d}_{\mathcal {A}}(f)< \frac {1}{2}\left (1-\frac {1}{2^{\frac {n}{k+1}}}\right )\), so it does not provide any useful information in that range. When it is positive, it is still always smaller than the lower bound in (8), only reaching equality when \(\mathrm {d}_{\mathcal {A}}(f)\) attains its maximum value, namely \(\frac {1}{2}\left (1-\frac {1}{2^{\frac {n}{2}}}\right )\). The upper bound in (7) does not depend on \(\mathrm {d}_{\mathcal {A}}(f)\), whereas the one in (10) increases continuously from 0 to \(\frac {1}{2}\left (1- \frac {1}{2^{(k-1)n/2}} \right )\) as \(\mathrm {d}_{\mathcal {A}}(f)\) increases from 0 to \(\frac {1}{2}\left (1-\frac {1}{2^{\frac {n}{2}}}\right )\).

We examine the tightness of the bounds in Theorem 2. The upper bound (9) cannot be reached (except for the trivial case \(\mathrm {d}_{\mathcal {A}}(f)=0\) and P_k(f) = 0) because Upper_n,k(x) < Upper_k(x) for 0 < x < 0.5. Note however that Upper_k(x) is the limit of Upper_n,k(x), as n approaches infinity. We found experimentally functions f for which P_k(f) is very close to the upper bound \({{\text {Upper}}}_{k}(\mathrm {d}_{\mathcal {A}}(f))\), while \(\mathrm {d}_{\mathcal {A}}(f)\) covers many values throughout the interval (0,0.5), see the last graph in the ??. We suspect therefore that this upper bound cannot be improved much (as a bound which is independent of n).

The examples below present functions for which the upper bound (10) as well as the lower bound in Theorem 2 are attained.

Summarising the examples above, for each fixed number of variables n and each odd k, the upper bound Upper_n,k in Theorem 2 is reached at nonlinearity \(\frac {1}{2^{n}}\) (which is the lowest possible non-zero nonlinearity) and if n is even, also at \(\frac {1}{2}\left (1-\frac {1}{2^{\frac {n}{2}}}\right )\) (which is the highest possible nonlinearity). The lower bound in Theorem 2 is reached for nonlinearities \(\frac {1}{2^{n}}\) as well as all nonlinearities of the form \(\frac {1}{2}\left (1-\frac {1}{2^{\frac {m}{2}}}\right )\) for m even, m ≤ n, i.e. \(\frac {1}{4}, \frac {3}{8}, \frac {7}{16}, \ldots \), for m = 2,4,6,…, respectively. In between these values, the lower bound might not be tight. Indeed for \(\mathrm {d}_{\mathcal {A}}(f)<\frac {1}{4}\), (6) provides a better lower bound for k = 3.

We conjectured in [11] that the lower bound (6) can be generalized to arbitrary odd k ≥ 3, as follows:

In the next section we will prove this conjecture.

The new lower bound in Corollary 8 is attained for k odd by some functions with nonlinearity in the range \(0<\mathrm {d}_{\mathcal {A}}(f)<\frac {1}{4}\) and for k even by some functions with \(0<\mathrm {d}_{{\mathscr{L}}}(f)<\frac {1}{4}\):

While not the purpose of this paper, we get an interesting consequence of the previous theorem, namely an upper bound for the moments of the Walsh coefficients.

In this section we focus on the test f(u₁ + ⋯ + u_k) + f(u₁) + ⋯ + f(u_k) = 0 for k even, and on the probability P_k(f) of failing this test. It is shown in [14] that f is linear if and only if P_k(f) = 0; moreover, f is affine if and only if P_k(f) ∈{0,1}. The test can therefore be used as a probabilistic affinity test as follows: run the test several times on f, and if f always passes the test (suggesting a probability of failure P_k(f) = 0), or f always fails the test (suggesting that P_k(f) = 1), then declare f to be affine. Note that f + 1 passes the linearity test above for some given tuples if and only if f fails the test for those same tuples; therefore we have P_k(f + 1) = 1 − P_k(f). Another way of looking at this affinity test is that we are testing both f and f + 1 for linearity, and if one of them passes all the tests and is declared linear then f can be declared affine. Any other linearity test could be used this way as an affinity test.

When f is not affine however (and therefore neither f nor f + 1 are linear), there are to our knowledge no results regarding the relationship of the probability P_k(f) of failing the test (for k even) and the nonlinearity \(\mathrm {d}_{\mathcal {A}}(f)\) of f; the existing lower and upper bounds on P_k(f) depend on \(\mathrm {d}_{{\mathscr{L}}}(f)\), the distance of f to the set of linear functions. Since this affinity test is equivalent to testing both f and f + 1 for linearity, it seems natural to consider both P_k(f) and P_k(f + 1) when examining a connection to \(\mathrm {d}_{\mathcal {A}}(f)\). We define and study its relation to \(\mathrm {d}_{\mathcal {A}}(f)\). Further motivation for this choice is given in Remark 12. For k = 2, we will prove lower and upper bounds for \(\overline {P}_{2}(f)\) in terms of the nonlinearity of f.

In Bellare et al. [1] lower and upper bounds were given for P₂(f) in terms of \(\mathrm {d}_{{\mathscr{L}}}(f)\). Namely, it was proven that where \(\mathrm {L}\mathrm {o}\mathrm {w}\mathrm {e}\mathrm {r}_{2}, \mathrm {U}\mathrm {p}\mathrm {p}\mathrm {e}\mathrm {r}_{2} : [0, \frac {1}{2}] \rightarrow \mathbb {R}\). The function Lower₂(x) is defined as (observe that \(\frac {3}{16},\frac {5}{16}\) are the two solutions of the equation \(3x-6x^{2}= \frac {45}{128}\), and so, since \(\frac {45}{128}>\frac {5}{16}\), then the value \(\mathrm {L}\mathrm {o}\mathrm {w}\mathrm {e}\mathrm {r}_{2}(x)=\frac {45}{128}\) is greater than 3x − 6x² on the interval \(\frac {5}{16} \le x \le \frac {45}{128}\)). The function Upper₂(x) is defined as Upper₂(0) = 0 and for x > 0

We now prove bounds for \(\overline {P}_{2}(f)\) in terms of \(\mathrm {d}_{\mathcal {A}}(f)\), the distance to the closest affine function, which is the natural parameter to consider when testing if a function is affine. Note that in the following theorem, although the bounds look similar to the bounds in (21) above, there is a subtle and important difference: the bounds are now a function of \(\mathrm {d}_{\mathcal {A}}(f)\), the distance to the closest affine function, whereas in (21) the bounds are expressed in terms of \(\mathrm {d}_{{\mathscr{L}}}(f)\), the distance to the closest linear function.

An improvement of the lower bound for the BLR linearity test (21) is given in [9]. Namely, it is shown that \(P_{2}(f)\ge H(\mathrm {d}_{{\mathscr{L}}}(f))\), where where for any constant \(0< c\le \frac {1}{2}\), g₁,g₂ are defined as

Note that this is indeed an improved lower bound as Lower₂(x) ≤ H(x) and the inequality is strict on the interval \(\left (\frac {45}{128}, \frac {1}{2}\right )\). The analogue of Theorem 11 holds for this improved bound as well.

The above affinity tests can be used to estimate the nonlinearity of a Boolean function. The probability of failing a test can be estimated by running the test several times and using statistical methods such as the binomial proportion confidence interval (see [14]). The bounds will then allow to give an interval for the value of the nonlinearity as per (1) and (2). For simplicity, we will assume that we have obtained an exact value for P_k(f) (in practice we will actually obtain a confidence interval). We will examine each test in turn. The graphs in the ?? will aid the discussion.

We first look at the affine test based on the BLR test, as described in Section 5. The first graph in the ?? displays the lower and upper bound described in Theorem 11. Thus, for values of \(0\le \overline {P}_{2}(f)< y^{(2)}_{1} = \frac {45}{128} = 0.3515625\) we can estimate the nonlinearity with good precision as being in the interval \( \mathrm {d}_{\mathcal {A}}(f)\in \left [{\mathrm {U}\mathrm {p}\mathrm {p}\mathrm {e}\mathrm {r}_{2}}^{-1}(\overline {P}_{2}(f)), {\mathrm {L}\mathrm {o}\mathrm {w}\mathrm {e}\mathrm {r}_{2}}^{-1}(\overline {P}_{2}(f))\right ]. \) The length of this interval increases with \(\overline {P}_{2}(f)\) to a length of approximately 0.058. For \( \overline {P}_{2}(f)=\frac {45}{128}\) we get For \(\frac {45}{128}< \overline {P}_{2}(f) <\frac {1}{4}\), \({\mathrm {L}\mathrm {o}\mathrm {w}\mathrm {e}\mathrm {r}_{2}}^{-1}(\overline {P}_{2}(f)) = \{\alpha ^{(2)}(\overline {P}_{2}(f)), {\upbeta }^{(2)}(\overline {P}_{2}(f)),\overline {P}_{2}(f)\} \), where \(0<\alpha ^{(2)}(y)\le {\upbeta }^{(2)}(y)< \frac {5}{16}\) are the two roots of the equation 3x − 6x² = y in this domain. We obtain two disjoint intervals where \(\mathrm {d}_{\mathcal {A}}(f)\) might be: Finally, for \(\overline {P}_{2}(f) \ge \frac {1}{4} \), the interval for \(\mathrm {d}_{\mathcal {A}}(f)\) is \(\left [{\mathrm {U}\mathrm {p}\mathrm {p}\mathrm {e}\mathrm {r}_{2}}^{-1}(\overline {P}_{2}(f)), \overline {P}_{2}(f)\right ]\). The estimate for \(\mathrm {d}_{\mathcal {A}}(f)\) becomes less and less precise (the interval length increases) as \(\overline {P}_{2}(f)\) increases. When \(\overline {P}_{2}(f)\) reaches \(\frac {1}{2}\), we obtain \(\mathrm {d}_{\mathcal {A}}(f) \in \left [\frac {1}{2\sqrt {6}}, \frac {1}{2}\right )\), an interval of length approximately 0.295.

Next we look at the nonhomomorphicity test f(u₁ + ⋯ + u_k) + f(u₁) + ⋯ + f(u_k) = 0 with odd k ≥ 3. We use the upper bound Upper_k described in Theorem 2 and the lower bound Lower_k described in Corollary 8, illustrated for k = 3,5 in the second and third graph in the ??.

As x increases in the interval [0,0.5], Upper_k(x) increases, whereas Lower_k(x) first increases from 0 to a local maximum \(y^{(k)}_{2}\), then decreases to a value of \(y^{(k)}_{1} = \frac {1}{2}\left (1-\frac {1}{2^{k-1}} \right )\) (reached for \(x=\frac {1}{4}\)) and increases again to 0.5. Consequently, we have three cases. When \(0\le P_{k}(f) < y^{(k)}_{1}\) we have that where for each 0 ≤ y ≤ 0.5 we denote by \(0<\alpha ^{(k)}(y)\le {\upbeta }^{(k)}(y)< \frac {1}{2}\) the two roots of the equation \(\frac {1}{2}\left (1- (1 - 2 x)^{k+1} - 2^{k+1}x^{k}(1-x)\right ) =y\). The length of this interval increases as P_k(f) increases from 0 to \(y^{(k)}_{1}\) (for illustration, it increases to a value of 0.028,0.016 and 0.011 for k = 3,5 and 7, respectively).

When \(y=P_{k}(f)\in [y^{(k)}_{1}, y^{(k)}_{2}]\), we have that Finally, for \(y^{(k)}_{2}<P_{k}(f)\le 0.5\), we have Note that the less tight bounds (7) from [14] would give the considerably less accurate estimate The length of the interval produced by our estimate (29) is

This quantity has a unimodal behavior: the length increases as a function of P_k(f), peaking at a value of achieved when and then decreases to 0, when P_k(f) reaches 0.5. For example, if k = 3,5,7, the length of the interval peaks at a value of 0.125,0.0741 and 0.05273, respectively (achieved when P_k(f) = 0.469,0.496 and 0.4995, respectively). The maximum length of the interval is achieved when P_k(f) is quite close to 0.5; the larger the value of k, the smaller the maximum length of the interval, that is, the more precisely we can estimate the nonlinearity.

We summarize these results in Table 1, which contains, for different values of k, the maximum length of the interval obtained when estimating the nonlinearity. The length is displayed firstly, for low values of P_k(f), namely the values in the interval \([0, y^{(k)}_{1}]\) discussed above. Secondly, the last column displays the maximum length of the interval for the remaining (higher) values of P_k(f).

We also present in Table 2 the estimate of the nonlinearity \(\mathrm {d}_{\mathcal {A}}\) that would be obtained by this method for a few examples of functions, and compare it with the true value of the nonlinearity. The examples in this table are the ones in Example 5, f(x₁,…,x_n) = x₁x₂ + ⋯ + x_m− 1x_m with m = 2,4,6,8 and n ≥ m and the functions in Example 9 of the type f(x₁,…,x_n) = x₁x₂⋯x_m with m = 3,4,5,6 and n ≥ m. We observe that for all these functions, the true value of the nonlinearity is at the top end of the estimated interval.

We also examined experimentally random functions in up to 9 variables (see the fourth figure in the ??), plotting the probability of failure P₃(f) as a function of the nonlinearity \(\mathrm {d}_{\mathcal {A}}(f)\). To obtain data for each possible value of the nonlinearity we started by randomly generating several functions for each possible weight lower than 0.5. We then computed their nonlinearity (for weights lower than 0.25 it is equal to the weight of the function, as the function is closer to the all-zero function than to any other affine function; for higher weights, the nonlinearity can be different from the weight, but many functions will have a nonlinearity close to their weight). We noticed that for functions in 7 or more variables most of the functions in our data have probability P₃ of failing the test close to the upper bound for P₃. This translates to the true value of the nonlinearity being at the low end of the estimated interval. We observed a similar situation for k = 5,7.

To conclude this section, we note that each test we considered is quite accurate in estimating nonlinearity when the probability of failing the test is small (and consequently the nonlinearity of the function is small), but the accuracy decreases as the probability of failing the test increases. If we were to apply different tests to the same function, we note that the estimated interval for the nonlinearity is least accurate when using the affinity test based on the BLR test. The tests based on (k + 1)-st order nonhomomorphicity with k odd have better accuracy, and this accuracy improves as k increases.