1 Introduction
Boolean functions are widely studied and they have applications in coding theory, cryptography and other fields. In cryptography, the properties of (vectorial) Boolean functions play a critical role, particularly when these functions are involved in the design of symmetric-key algorithms, such as block ciphers (in S-boxes) and stream ciphers (in nonlinear filters and combiners). When designing a cryptosystem, we want it to resist most of the known attacks. For this reason, a lot of effort is required to find a Boolean function with good cryptographic properties.
Various criteria can be used to measure the ability of Boolean functions to resist some cryptanalysis. For instance, balancedness, high nonlinearity and good autocorrelation properties provide good resistance to linear cryptanalysis and differential cryptanalysis [
8]. It is not easy to find a function satisfying many such criteria at once, but usually we try to achieve a reasonable compromise by focusing on a few particular properties. In this paper, we study the weight, balancedness and nonlinearity of a particular class of Boolean functions that we call “splitting” functions. We study the same properties also for cubic Boolean functions that are not necessarily splitting functions. By “splitting” functions we refer to those Boolean functions that can be written as the sum of two Boolean functions defined over disjoint sets of variables, that is,
\(f(x_1,\ldots ,x_n)=g(x_1,\ldots ,x_s)+h(x_{s+1},\ldots ,x_n)\).
This paper is organised as follows. Sect.
2 reports some known preliminary results. In Sect.
3, we show how the weight of any Boolean function can be related to the weights of some other functions with lower dimension. In addition, we prove some results on the weight and balancedness of splitting functions, and of a special class of cubic Boolean functions. This allows us to present a procedure for computing the weight of a (generic) cubic Boolean function. In Sect.
4, we present an inequality which relates the nonlinearity of any Boolean function to the nonlinearity of some other functions of lower dimension. Finally, we compute the nonlinearity of splitting functions with a given shape.
2 Preliminaries
In this section we report some definitions and results which we use in our work. For more details, the reader is referred to [
1,
2,
4,
5,
7,
9].
The symbol \(\mathbb N\) denotes the set of natural numbers. Throughout the paper, unless otherwise specified, n denotes a positive integer. We denote the field of two elements by \(\mathbb {F}\), and the vector space of dimension n over \(\mathbb F\), for \(n\in \mathbb N\), by \(\mathbb F^n\). The vectors in \(\mathbb F^n\) denoted by \(0_n\) and \(1_n\) are the vectors whose entries are, respectively, all zeros and all ones. Given a set A, |A| denotes its size.
A vectorial Boolean function (vBf) is any function F from \(\mathbb {F}^n\) to \(\mathbb {F}^m\), for some positive integers n, m. A Boolean function (Bf) is any function f from \(\mathbb {F}^n\) to \(\mathbb {F}\), for some \(n\ge 1\). Thus, Boolean functions are vectorial Boolean functions with \(m=1\). A vBf can be viewed as a concatenation of Bf’s. Indeed, we can write a vBf as \(F=(f_1,\ldots ,f_m)\), where the Bf’s \(f_1,\ldots ,f_m\) are called the coordinate functions of F.
In the present paper, we focus on Boolean functions. For \(n\ge 1\), we denote by \(B_n\) the set of all Boolean functions from \(\mathbb F^n\) to \(\mathbb F\). For \(1\le k<n\), if f is in \(B_n\) and depends only on k variables, we denote by \(f_{\restriction \mathbb {F}^k}\) its restriction to these k variables. Clearly, \(f_{\restriction \mathbb {F}^k}\) is in \(B_k\).
We use the algebraic normal form (ANF for short) to represent Bf’s. This representation is unique and, given
\(f\in B_n\), it is the
n-variate polynomial representation over
\(\mathbb {F}\) given by
$$\begin{aligned} f(x_1,\ldots ,x_n)=\sum _{I\subseteq \mathcal {P}}a_I\left( \prod _{i\in I}x_i\right) , \end{aligned}$$
where
\(\mathcal {P}=\{1,\ldots ,n\}\) and
\(a_I\in \mathbb {F}\). When
\(a_I\ne 0\), the element
\(\prod _{i\in I}x_i\) is called a
term of
f. The
algebraic degree or simply
degree of
f can be defined as the value
$$\begin{aligned} \deg (f)=\max _{\begin{array}{c} I\subseteq \mathcal {P}\\ a_I\ne 0 \end{array}}|I|. \end{aligned}$$
We say that
f is
linear if
\(\deg (f)\le 1\) and
\(f(0)=0\),
affine if
\(\deg (f)\le 1\),
quadratic if
\(\deg (f)\le 2\) and
cubic if
\(\deg (f)\le 3\).
Consider \(f\in B_n\), for a positive integer n. The Hamming weight of f is given by \(\mathrm {w}(f)=|\{x\in \mathbb {F}^n\mid f(x)=1\}|\), and we say that f is balanced if \(\mathrm {w}(f)=2^{n-1}\). All non-constant affine functions are balanced. The distance between f and g is \(d(f,g)=\mathrm {w}(f+g)\) and the nonlinearity of f is \(\mathcal {N}(f)=\min _{\alpha \in A_n}d(f,\alpha )\), where \(A_n\) is the set of all affine Boolean functions in n variables.
The
Walsh transform of
f is the function
\(\mathcal {W}_f\) from
\(\mathbb {F}^n\) to
\(\mathbb {Z}\), defined as
$$\begin{aligned} \mathcal {W}_f(a)=\sum _{x\in \mathbb {F}^n}(-1)^{f(x)+a\cdot x}\,, \end{aligned}$$
for all
\(a \in \mathbb {F}^n\) and where “
\(\cdot\)” is any inner product in
\(\mathbb F^n\). We define
\(\mathcal {F}(f)\) as
$$\begin{aligned} \mathcal {F}(f)=\mathcal {W}_f(0)=\sum _{x\in \mathbb {F}^n}(-1)^{f(x)}=2^n-2\mathrm {w}(f). \end{aligned}$$
Observe that
f is balanced if and only if
\(\mathcal {F}(f)=0\).
The nonlinearity of a Bf f can also be expressed as \(\mathcal {N}(f)=2^{n-1}-\frac{1}{2}\mathcal {L}(f)\), where \(\mathcal {L}(f)=\max \limits _{a\in \mathbb {F}^n}|\mathcal {W}_f(a)|\). A Bf f on n variables is called bent if \(\mathcal {N}(f)=2^{n-1}-2^{\frac{n}{2}-1}\) (this can only happen for n even). The lowest possible value of \(\mathcal {L}(f)\) is \(2^{\frac{n}{2}}\), and the bent functions are precisely those that meet this bound with equality. For n odd, a Bf f is called semi-bent if \(\mathcal {N}(f)=2^{n-1}-2^{\frac{n-1}{2}}\).
Let
\(a\in \mathbb {F}^n\). The
first-order derivative, or simply the derivative, of
\(f\in B_n\) in the direction of
a is defined by
$$\begin{aligned} D_af(x)=f(x+a)+f(x). \end{aligned}$$
The following result is well known, see for instance [
4] Theorem 12.
Two Bf’s
\(f,g\in B_n\) are said to be
affine equivalent if there exists an affine automorphism
\(\varphi :\mathbb {F}^n\rightarrow \mathbb {F}^n\) such that
\(f=g\circ \varphi\). This relation is denoted by
\(\sim _A\) and we write
\(f\sim _A g\). Observe that
\(\sim _A\) is an equivalence relation. The following results are well known, for example they can be derived from Proposition 13 in [
4].
Next we present a well-known theorem on classification of quadratic Boolean functions, see [
7] page 438. This representation of quadratic Bf’s is sometimes called
Dickson form. Indeed, Dickson calculated explicitly the Hamming weight of quadratic functions, by showing that any non-affine quadratic Boolean function
\(f\in B_n\) is affine equivalent to
\(x_1x_2+\cdots + x_{2k-1}x_{2k}+cx_{2k+1}+d\), with
\(c,d\in \mathbb {F}\) and
\(2k\le n\) (if
\(c=1\), then
\(2k+1\le n\)).
The proofs of the next theorem and lemma can be found in [
6] page 134.
The following result is well known.
3 On the weight of Boolean functions
In this section we study Boolean functions of a particular form that we call splitting functions. Splitting functions can be characterised by means of Boolean functions of lower dimensions. By studying properties of these latter functions, we can determine important properties of the splitting function.
In particular, in this section we classify the weight of splitting functions and the weight of Boolean functions of degree three. Moreover, we determine some conditions for the balancedness of these functions.
We study here the weight and balancedness of splitting Bf’s.
It is immediate from Remark
12 and Theorem
13 that the following corollary holds.
We consider the balancedness of splitting functions.
In the following proposition we consider splitting functions of a special form. This allows us to compute the exact value of their weights.
Observe that the function
f in Proposition
18 is balanced if and only if
\(m=1\), that is,
f is balanced if and only if it is a linear function.
3.1 The weight computation of twisted products
In this subsection, we study the weight and balancedness of the twisted products of Bf’s. We show how the weight of a Bf on n variables can be related to the weights of some other functions of lower dimension. For ease of notation, in this subsection we consider Boolean functions on \(n+1\) and \(n+m\) variables, for \(n,m\in \mathbb N\).
Any Bf in
\(n+1\) variables can be expressed in the form
$$\begin{aligned} f\sim _A x_{n+1}g^\prime (x_1,\ldots ,x_n)+h^\prime (x_1,\ldots ,x_n), \end{aligned}$$
(3.1)
for
\(g^\prime ,h^\prime \in B_n\). Observe that
\(x_{n+1}g^\prime (x_1,\ldots ,x_n)+h^\prime (x_1,\ldots ,x_n)=x_{n+1}(g^\prime +h^\prime )+(1+x_{n+1})h^\prime\). So any Bf
f in
\(n+1\) variables can be written in the form
$$\begin{aligned} f\sim _A x_{n+1}g(x_1,\ldots ,x_n)+(1+x_{n+1})h(x_1,\ldots ,x_n), \end{aligned}$$
(3.2)
for
\(g,h\in B_n\). Given (
3.2), we say that
f is the
twisted product of
g and
h. Observe that the twisted product is a special case of the form defined by
$$\begin{aligned} f\sim _A \left( \prod _{j=1}^mx_j\right) g(x_{m+1},\ldots ,x_{m+n})+\left( 1+\prod _{j=1}^mx_j\right) h(x_{m+1},\ldots ,x_{m+n}), \end{aligned}$$
(3.3)
for some positive integers
m,
n and Bf’s
g and
h depending on
n variables.
Next we show that if we know the weights of g and h, then we can obtain the weight of f.
Finally, we consider the weight of cubic Bf’s. Generally, it is difficult to determine the weight for Bf’s of degree greater than 2 (problem addressed for example in [
3]). In the following proposition, we present a result which completely describes the weight of a special class of cubic functions. Using Theorem
6 and Remarks
19 and
23, the proof of Proposition
24 is a direct case-by-case computation. For this reason, we omit the proof.
Thanks to Proposition
24, we deduce the following corollary which gives a description of all balanced cubic functions of the class
\(f=x_{n+1}g(x_1,\ldots ,x_n)+(1+x_{n+1})h(x_1,\ldots ,x_n)\), with
\(\deg (g),\deg (h)\le 2\).
Corollary
25 can be restated as follows.
3.2 The weight of cubic Boolean functions
Finally, we consider generic cubic Bf’s, not only those that can be expressed as in Proposition
24. In this last part we go back to considering Bf’s on
n variables. When a Bf
\(f\in B_n\) is expressed in the form (
3.1), that is,
\(f=x_1g(x_2,\ldots ,x_n)+h(x_2,\ldots ,x_n)\), we have
$$\begin{aligned} \mathrm {w}(f)=\mathrm {w}((g+h)_{\restriction \mathbb {F}^{n-1}})+\mathrm {w}(h_{\restriction \mathbb {F}^{n-1}}). \end{aligned}$$
(3.5)
Therefore, to determine the weight of
f, we can simply compute the weight of
\((g+h)_{\restriction {\mathbb F^{n-1}}}\) and of
\(h_{\restriction {\mathbb F^{n-1}}}\). Since we are considering cubic functions, then
g is quadratic and
h can be affine, quadratic or cubic. If
h is affine or quadratic, then
\(\deg (g+h),\deg (h)\le 2\) and the weight of
f is already described in Proposition
24. On the other hand, if
h is cubic, then
\(g+h\) is also cubic and Proposition
24 cannot be directly applied. However, we can recursively repeat the process of decomposing
f so that its weight is computed as the sum of the weights of some affine or quadratic functions. We now show how this can be done. Set
\(f=x_1g_1(x_2,\ldots ,x_n)+h_1(x_2,\ldots ,x_n)\) with
\(\deg (h_1)=3\). Then, we can write
\(h_1\) as
\(h_1=x_2g_2(x_3,\ldots ,x_n)+h_2(x_3,\ldots ,x_n)\), where
\(\deg (g_2)\le 2\) and
\(\deg (h_2)\le 3\). We do the same for
\(g_1\), hence
\(g_1=x_2g'_2(x_3,\ldots ,x_n)+h'_2(x_3,\ldots ,x_n)\), where
\(\deg (g'_2)\le 1\) and
\(\deg (h'_2)\le 2\). Therefore,
\(g_1+h_1=x_2(g_2+g'_2)+h_2+h'_2\). Notice that the cubic terms of
\(h_1\) coincide with those of
\(g_1+h_1\). So
$$\begin{aligned} \mathrm {w}&({h_1}_{\restriction {\mathbb F^{n-1}}})=\mathrm {w}((g_2+h_2)_{\restriction {\mathbb F^{n-2}}})+\mathrm {w}({h_2}_{\restriction {\mathbb F^{n-2}}}),\\ \mathrm {w}&((g_1+h_1)_{\restriction {\mathbb F^{n-1}}})=\mathrm {w}((g_2+h_2+g'_2+h'_2)_{\restriction {\mathbb F^{n-2}}})+\mathrm {w}((h_2+h'_2)_{\restriction {\mathbb F^{n-2}}}). \end{aligned}$$
If the degree of
\(h_2\) is smaller than 3, the weights of
\((g_1+h_1)_{\restriction {\mathbb F^{n-1}}}\) and of
\({h_1}_{\restriction {\mathbb F^{n-1}}}\) are described in Proposition
24. Otherwise, we continue with the decomposition of the functions, namely
\(h_2,g_2,h'_2,g'_2\), e.g.
\(h_2=x_3g_3(\ldots )+h_3(\ldots )\), and we recursively apply the same approach. Every decomposition step doubles the number of functions for which we want to compute the weight. Notice that the variables that determine the decomposition of the Bf, namely
\(x_1,x_2,\ldots\) in the computations above, should be selected in such a way as to minimize the number of recursive steps needed. Our choice is to select the variable which occurs most frequently in
\(\mathrm{Term}_3(h_i)\), where
\(\mathrm{Term}_3(h_i)\) is the set of all cubic terms of
\(h_i\). Other choice strategies are possible and we do not claim that our strategy is optimal. We leave it as an open problem. To simplify the description of the procedure, we call
quadratic representation the final decomposition of the involved cubic Boolean functions.
We use this idea to build an algorithm that computes the weight of any cubic Bf.
We now briefly discuss the complexity of determining the weight of a cubic Boolean function using the above algorithm. Suppose that we are able to obtain a function
\(h_t\) of degree at most 2 after
t iterations of the decomposition. Therefore, we end up with
\(2^t\) functions of degree at most 2, defined over
\(\mathbb F^{n-t}\), whose weight we have to compute. We performed some computational experiments to estimate the value of
t. In Table
1 we report the average value of
t for 200 randomly-generated cubic Boolean functions over
\(\mathbb F^n\), with
n varying from 5 to 100. Since we are only interested in the cubic terms of a cubic Bf, to generate it we selected randomly an integer
r between 1 and the number of possible cubic terms, and then we selected
r cubic terms at random. The decompositions were performed using the strategy described in Algorithm
1.
Table 1
Average value t of the number of decompositions needed to reduce a randomly-generated cubic Bf in \(B_n\) into a quadratic representation
5 | \(n-4\) | 30 | \(n-6\) | 55 | \(n-7\) | 80 | \(n-7\) |
10 | \(n-5\) | 35 | \(n-6\) | 60 | \(n-7\) | 85 | \(n-7\) |
15 | \(n-6\) | 40 | \(n-7\) | 65 | \(n-7\) | 90 | \(n-7\) |
20 | \(n-6\) | 45 | \(n-7\) | 70 | \(n-7\) | 95 | \(n-7\) |
25 | \(n-6\) | 50 | \(n-7\) | 75 | \(n-7\) | 100 | \(n-8\) |
The values reported in Table
1 are quite accurate. For example, in the case
\(n=100\) the minimum value obtained is 44, the maximum 96, the mean is 92.115 and the variance is 39.222.
In Table
2 we report the results obtained when considering 200 randomly-selected cubic Boolean functions with more sparse terms, that is,
\(f\in B_n\) cubic with at most
\(n^2\) cubic terms. The functions are generated as described previously, with the number of possible cubic terms restricted by
\(1\le r\le n^2\). As before, the decompositions were performed using the strategy described in Algorithm
1. We show in the table that, for the values of
n considered, the average number of decompositions needed is around
\(\frac{3}{4}n\).
Table 2
Average value t of the number of decompositions needed to reduce a randomly-generated cubic Bf in \(B_n\) (with at most \(n^2\) cubic terms) into a quadratic representation
5 | 2 | 3 | 30 | 19 | 22 | 55 | 40 | 41 | 80 | 61 | 60 |
10 | 5 | 7 | 35 | 23 | 26 | 60 | 43 | 45 | 85 | 65 | 63 |
15 | 8 | 11 | 40 | 27 | 30 | 65 | 48 | 48 | 90 | 70 | 67 |
20 | 12 | 15 | 45 | 31 | 33 | 70 | 50 | 52 | 95 | 74 | 71 |
25 | 16 | 18 | 50 | 35 | 37 | 75 | 57 | 56 | 100 | 77 | 75 |
Similarly to the previous table, the values reported in Table
2 are quite accurate. For example, in the case
\(n=100\) the minimum value obtained is 15, the maximum 87, the mean is 77.25 and the variance is 151.4275. We leave it as an open problem to investigate the effectiveness of our method for Boolean functions with other restrictions on
\(\mathrm{Term}_3\).
We now study the complexity of determining the weight of a quadratic Bf.
(a)
We consider the following operations to be elementary: bit addition, bit multiplication, variable multiplications (e.g. \(x_1\cdot x_2\rightarrow x_1x_2\)). The goal of our final estimate will be in terms of elementary operations with the big O notation.
(b)
We recall that given a quadratic
\(g\in B_k\), we can obtain an affine equivalent map as in Theorem
6. This result is well known, see for instance [
4], Subsection 5.2.1. Indeed, if
\(x_1x_2\) is a term of
g, then
\(g=x_1x_2+x_1g_1(x_3,\ldots ,x_k)+x_2g_2(x_3,\ldots ,x_k)+g_{1,2}(x_3,\ldots ,x_k)\), for some
\(g_1,g_2,g_{1,2}\) with
\(\deg (g_1),\deg (g_2)\le 1\) and
\(\deg (g_{1,2})\le 2\). Hence
\(g=(x_1+g_2)(x_2+g_1)+g_1g_2+g_{1,2}\) is affine equivalent to
\(x_1x_2+g_1g_2+g_{1,2}\). Applying this method recursively, in at most
k/2 iterations we obtain an affine equivalent map as in Theorem
6, and using Remark
19 we compute the weight of
g. In the following, we will use the word
(decomposition) step to refer to one of the above iterations.
(c)
Now we analyse the r-th decomposition step of (b). In this step, we consider a quadratic term in g, namely \(x_ix_j\).
We consider the representation of g as \(g=x_ix_j+x_ig_i+x_jg_j+g_{i,j}\).
Notice that, since we are at the r-th step of the decomposition, \(g_i,g_j,g_{i,j}\) depend on at most \({k-2r}\) variables and \(g_i,g_j\) have at most \(k-2r+1\) terms. From the ANF of g we determine \(g_i,g_j\) and \(g_{i,j}\). Indeed, \(g_{i,j}=g(x_i=0,x_j=0)\), \(g_i=g(x_i=1,x_j=0)+g_{i,j}\) and \(g_j=g(x_i=0,x_j=1)+g_{i,j}\), where, with abuse of notation, \(g(x_i=a,x_j=b)\) indicates that we consider the ANF of g with the substitutions \(x_i=a\) and \(x_j=b\). In the \((r+1)\)-th step we will consider \(g\leftarrow g_ig_j+g_{i,j}\).
(d)
We now evaluate the complexity of every computation in the r-th step. The cost of computing \(g_{i,j}\) is bounded by the cost of performing a full evaluation \(g(a_1,\ldots ,a_k)\), which itself is bounded by \(k^2\) multiplications and \(k^2\) additions. The cost for \(g_i,g_j\) is similar, but we have to add \(k^2\) additions. So the overall cost of computing \(g_i,g_j,g_{i,j}\) is bounded by the cost of performing \(8k^2\) elementary operations. The multiplication of the two linear polynomials \(g_i\) and \(g_j\) costs at most \(k^2\) variable multiplications, since they have at most \(k-2r-1\) terms. Therefore the computation of the input of the next step (the new g) is bounded by \(9k^2\) elementary operations.
(e)
Hence, from (b) and (d), we conclude that the cost of determining the weight of a quadratic Bf in k variables is at most \(\mathrm{cost}_k=9k^2\cdot \frac{k}{2}=\frac{9}{2} k^3\le 5k^3\) elementary operations.
(f)
Therefore, by considering \(k=n-t\), the complexity of computing the weight of a cubic f is at most \(2^t\cdot \mathrm{cost}_{n-t}=2^t\cdot \frac{9}{2}(n-t)^3\) elementary operations.
(g)
If we consider
\(t\approx \frac{3}{4}n\) (as we saw in Table
2) we have
\(2^{\frac{3}{4}n} cost_{n/4}\approx O(2^{\frac{3}{4}n}(n/4)^3)=O(2^{\frac{3}{4}n}n^3)\).
We now compare the complexity of Algorithm
1 with the complexity of computing the weight of a Boolean function with some other methods. For a more general overview, we also consider methods admitting distinct types of input (Algorithm
1 takes as input the ANF of a Boolean function). Recall that the truth table of
\(f\in B_n\) is
\(T_f=[f(u) : u \in {\mathbb {F}}^{n}]\). So, to compute the weight of
f we can count how many 1’s appear in
\(T_f\).
-
If for input we have the truth table of f, the cost is at most \(2^n\) additions.
-
If for input we have some information on the Walsh transform, in particular its value in zero, the computation is immediate (\(\mathcal {W}_f(0)=2^n-2\mathrm {w}(f)\)).
-
If for input we have the ANF of f, either we compute the truth table (the cost is at least \(2^n\) evaluations), or we can compute the Walsh transform in zero (again the cost is \(2^n\) evaluations).
Therefore, according to our estimates, given the ANF of a cubic Boolean function with a limited number of cubic terms, as described in Table
2, our algorithm is more efficient than the other known procedures described.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.