1 Introduction

Boolean functions are central objects for the design and the security of symmetric cryptographic systems (stream ciphers and block ciphers). Boolean functions used in ciphers must satisfy some specific properties to resist different attacks. One of the most important properties of Boolean functions in Linear Feedback Shift Registers (LFSR) based stream ciphers is correlation immunity introduced by Siegenthaler^[1]. For Boolean functions used in block ciphers, the most important properties are nonlinearity and differential characteristics (propagation degree, global avalanche characteristics (GAC) and so on) based on the auto-correlation or cross-correlation functions of Boolean functions. Construction of correlation immune and resilient (balanced correlation immune) functions has been an interesting research area from mid 1980s^[2-6]. Zhang et al.^[7-8] constructed an almost optimal resilient function on a large even number of variables by using several sets of disjoint spectra functions on a small number of variables. Along all paper, we apply actively auto-correlation or cross-correlation functions for the investigation of Boolean functions.

The strict avalanche criterion (SAC) and the propagation criterion (PC) are employed as a measure of the propagation characteristics of Boolean functions. They are very important concepts in designing cryptographic functions employed by data encryption algorithms and one-way hashing functions. However, SAC and PC capture only the local properties of Boolean functions. In order to measure the global properties of Boolean functions, Zhang and Zheng^[9] introduced GAC and gave a lower bound and an upper bound on the two indicators, respectively. But the GAC is used to measure only one Boolean function, so as to measure the cross-correlation of two different Boolean functions from the confusion and the diffusion aspects. Zhou et al.^[10-11] proposed the GAC of two Boolean functions, and deduced the tight lower and the tight upper bounds on the two indicators. Tang et al.^[12] gave a method to construct balanced Boolean functions and the constructed functions possessed the best GAC property. Zhou et al.^[13-14] studied the lower bound on the sum-of-squares indicator of balanced functions obtained by Son et al.^[15], and introduced a new general class of balanced Boolean functions with optimal auto-correlation distribution.

It is always an important problem to construct Boolean functions with good cryptographic properties. Concatenation is an important method by which we can construct Boolean functions with good cryptographic properties.

2 Preliminaries

In this section we introduce some basic concepts and notations. Let F₂ denote the finite field with two elements. We denote by B_n the set of all Boolean functions n variables, i.e., of all the functions from F₂ⁿ into F₂. To avoid confusion with the additions of integers in R, denoted by + and Σ_i, we denote by ⊕ the additions in F₂,F₂ⁿ and B_n.

The Hamming weight wt(x) of an element x=(x₁,x₂,…,x_n)∈F₂ⁿ is the number of ones in x. We say that a Boolean function is balanced if its truth table contains an equal number of 0's and 1's, that is, if its Hamming weight equals wt(f)=2^n－1. The Hamming distance between two functions f(x) and g(x), denoted by d(f, g), is the Hamming weight of f⊕g, i.e.,d(f, g)=wt(f⊕g).

Any Boolean function f(x)∈B_n, where x=(x₁,x₂,…,x_n)∈F₂ⁿ is generally represented by its algebraic normal form(ANF)：

$f({x_1},{x_2}, \cdots ,{x_n}) = \mathop \oplus \limits_{u \in F_2^n} {\lambda _u}\left( {\prod\limits_{i = 1}^n {x_i^{{u_i}}} } \right)$

where λ_u∈F₂ and u=(u₁,u₂,…,u_n)∈F₂ⁿ. The algebraic degree of f(x), denoted by deg(f), is the maximal value of wt(u) such that λ_u≠0. A Boolean function is affine if there does not exist term of degree strictly greater than 1 in the ANF and the set of all affine functions is denoted by A_n. An affine function with constant term equal to zero is called a linear function. Any liner function on F₂ⁿ is denoted by

$x \cdot w = {x_1}{w_1} \oplus {x_2}{w_2} \oplus \cdots \oplus {x_n}{w_n}$

where x, w∈F₂ⁿ. The nonlinearity of an n-variable function f(x) is nl(f)= $\mathop {\min }\limits_{g \in {A_n}} \left( {d\left( {f, g} \right)} \right)$ , i.e., the minimal Hamming distance from the set of all n-variable affine functions. The Walsh transform of f(x)∈B_n is a real valued function over F₂ⁿ which is defined as

${W_f}\left( w \right) = \sum\limits_{x \in F_2^n} {{{\left( { - 1} \right)}^{f\left( x \right) \oplus w \cdot x}}} $

(1)

The value of Walsh transform is also called the spectral distribution or simply the spectrum of a Boolean function. It is an important tool for the analysis of Boolean functions. It is well known that

$nl\left( f \right) = {2^{n - 1}} - \frac{1}{2}L\left( f \right)$

where $L\left( f \right) = \mathop {\max }\limits_{w \in F_2^n} \left| {{W_f}\left( w \right)} \right|$ . For n even, a function of n variables is called bent^[16] if W_f(w)=±2^n/2 for all w∈F₂ⁿ. These functions are important in both cryptography and coding theory since they achieve the maximum nonlinearity among all n-variable functions.

Correlation immune functions were introduced by Siegethaler^[1], to withstand a class of divide-and-conquer attacks on combine model of stream ciphers. Xiao and Massey^[17] proved a spectral characterization of correlation immune functions. Here, we state this characterization as the definition of correlation immunity.

Definition 1^[17] An n-variable Boolean function f(x)∈B_n is mth-order correlation immune if and only if its Walsh transform satisfies W_f(w)=0, for 0 ＜wt(w)≤m, w∈F₂ⁿ.

Note that f(x) is balanced if and only if W_f(0)=0. Balanced mth-order correlation immune functions are called m-resilient functions. Thus, a function f(x) is m-resilient if and only if its Walsh transform satisfies

${W_f}\left( w \right) = 0, for0 \le wt\left( w \right) \le m$

In this paper, by an (n, m, d, x) function we denote an n-variable, m-resilient function with degree d and nonlinearity x. In the above notation, a component is replaced by a “-” if it is not specified, e.g.,(n, m, d,-) if the nonlinearity is not specified.

Definition 2 The cross-correlation function between two Boolean functions f(x), g(x)∈B_n,x∈F₂ⁿ is an integer-valued function Δ_{f, g}(α): F₂ⁿ→[－2ⁿ,2ⁿ] defined by

${\Delta _{f, g}}\left( \alpha \right) = \sum\limits_{x \in F_2^n} {{{\left( { - 1} \right)}^{{D_{f, g}}\left( \alpha \right)}}} $

where α∈F₂ⁿ,D_{f, g}(α)=f(x)⊕g(x⊕α) is called the derivative of f(x) and g(x) in the direction of α∈F₂ⁿ.

In case f(x)=g(x) in Definition 2, the cross-correlation function Δ_{f, f}(α) is called the auto-correlation function of f(x) at α and denoted by Δ_f(α).

A Boolean function f(x) satisfies the propagation criterion PC(p) of degree p,1≤p≤n if Δ_f(α)=0, for 1≤wt(α)≤p. If f(x) is a bent function, then Δ_f(α)=0 for all non-zero α∈F₂ⁿ. Hence bent functions satisfy PC(n).

Definition 3^[10] Let f(x), g(x)∈B_n. The sum-of-squares indicator of the cross-correlation between f(x) and g(x) is defined by

${\sigma _{f, g}} = \sum\limits_{a \in F_2^n} {\Delta _{f, g}^2\left( a \right)} $

the absolute indicator of the cross-correlation between f(x) and g(x) is defined by

${\Delta _{f, g}} = \mathop {\max }\limits_{a \in F_2^n} \left| {{\Delta _{f, g}}\left( a \right)} \right|$

The above indicators are called the GAC between two Boolean functions. Zhou et al.^[10] got

$0 \le {\Delta _{f, g}} \le {2^n},{({\Delta _{f, g}}\left( 0 \right))^2} \le {\sigma _{f, g}} \le {2^{3n}}$

If f(x)=g(x), then

${\sigma _f} = \sum\limits_{a \in F_2^n} {\Delta _f^2\left( a \right)} ,{\Delta _f} = \mathop {\max }\limits_{a \in F_2^n, a \ne 0} \left| {{\Delta _f}\left( a \right)} \right|$

The smaller σ_f and Δ_f are, the better the GAC of a Boolean function is. Zhang and Zheng^[9] also derived bounds on two indicators:

$0 \le {\Delta _f} \le {2^n},{2^{2n}} \le {\sigma _f} \le {2^{3n}}$

and also showed that two lower bounds are achieved by bent functions. Definition 3 implies that the smaller Δ_{f, g} and σ_{f, g} are, the better the uncorrelation between f(x) and g(x) is.

By using the previous definitions, we give some simple results. These results state some of the basic properties of the auto-correlation function, cross-correlation function and the sum-of-squares indicator. The proof is just routine verification from the definition.

Proposition 1 Let f, g∈B_n for the complement function of f we use the notation f, i.e.,f=1⊕f.

Then

$\begin{array}{*{20}{c}} {{\Delta _f}\left( \alpha \right) = {\Delta _{\bar f}}\left( \alpha \right),{\Delta _{f, g}}\left( \alpha \right) = {\Delta _{g, f}}\left( \alpha \right) = {\Delta _{\bar f,\bar g}}\left( \alpha \right)}\\ {{\Delta _{f,\bar g}}\left( \alpha \right) = - {\Delta _{f, g}}\left( \alpha \right),{\Delta _{f,\bar f}}\left( \alpha \right) = - {\Delta _f}\left( \alpha \right)}\\ {{\Delta _{\bar f,\bar f}}\left( \alpha \right) = {\Delta _f}\left( \alpha \right),{\sigma _f} = {\sigma _{\bar f}},{\sigma _{f,\bar g}} = {\sigma _{f, g}}}\\ {{\sigma _{f,\bar f}} = {\sigma _{\bar f,\bar f}} = {\sigma _f}} \end{array}$

3 GAC of f₁‖f₂

In this section, we will use concatenation of Boolean functions. Let f₁,f₂∈B_n－1 and f(x)∈B_n. Then by concatenation of f₁ and f₂, we mean that the output columns of the truth tables of f₁,f₂ are concatenated to provide the output column of the truth table of an n-variable function.

We denote the concatenation of f₁,f₂ by f₁‖f₂. So,f=f₁‖f₂ has the in algebraic normal form

$\begin{array}{*{20}{c}} {f({x_1},{x_2}, \cdots ,{x_n}) = {f_1}({x_1},{x_2}, \cdots ,{x_{n - 1}}) \oplus {x_n}\left( {{f_1}\left( {{x_1},} \right.} \right.}\\ {{x_2}, \cdots ,{x_{n - 1}}) \oplus {f_2}\left. {({x_1},{x_2}, \cdots ,{x_{n - 1}})} \right).} \end{array}$

In Ref.^[11], the relationship among σ_f and σ_f1,σ_f2 was given by using the definition of auto-correlation function.

Lemma 1^[11] Let f(x, x_n)=f₁‖f₂∈B_n,x∈F₂^n－1,x_n∈F₂,f₁,f₂∈B_n－1, then

${\sigma _f} = {\sigma _{{f_1}}} + {\sigma _{{f_2}}} + 6{\sigma _{{f_1},{f_2}}}$

(2)

According to Lemma 1, a function f(x)∈B_n is constructed with a lower bound on σ_f by choosing the proper component functions f₁,f₂ in Ref.^[11]. For the function f, we have

Theorem 1 Let f be a (n, m, n－m－1,2^n－1－2^m+1) function with f=f₁‖f₂, where f₁,f₂ are (n－1,m, n－m－2,－) functions,m ＞ n/2－2.Then Δ_f1,f2(α)=0 for all α∈F₂^n－1.

Proof From Ref.^[18], we know that the Walsh transforms of f,f₁,f₂ are three-valued 0,±2^m+2. We shall compute the σ_f and σ_f1,σ_f2, respectively.

Let k be the number of elements α such that W_f(α)=0. By Parseval's equation $\sum\limits_{a \in F_2^n} {W_f^2\left( \alpha \right)} = {2^{2n}}$ , we have

$({2^n} - k){2^{2m + 4}} = {2^{2n}}$

thus,k=2ⁿ－2^2n－2m－4. According to the formula ${\sigma _f} = {2^{ - n}}\sum\limits_{\alpha \in F_2^n} {W_f^4\left( \alpha \right)} $ ^[19], we obtain

$\begin{array}{*{20}{c}} {{\sigma _f} = {2^{ - n}}\sum\limits_{\alpha \in F_2^n} {W_f^4\left( \alpha \right)} = {2^{ - n}}\left( {{2^n} - k} \right){2^{4m + 8}} = }\\ {{2^{ - n}}{2^{2n - 2m - 4}}{2^{4m + 8}} = {2^{n + 2m + 4}}} \end{array}$

Similarly, we get σ_f1=σ_f2=2^n+2m+3. Thanks to Lemma 1, we have

${2^{n + 2m + 4}} = {2^{n + 2m + 3}} + {2^{n + 2m + 3}} + 6{\sigma _{{f_1},{f_2}}}$

therefore,σ_f1,f2=0. As,σ_f1,f2=∑_{α∈F2^n－1}Δ_f1,f2²(α),

thus

${\Delta _{{f_1},{f_2}}}\left( \alpha \right) = 0$

for all α∈F₂^n－1.

Remark

1-1 We know that if f₁ and f₂ are (n－1,m,－,－), then f=f₁‖f₂ is (n, m,－,－). This was proved by Camion et al. in Ref.^[2]. In the above theorem, the f,f₁ and f₂ have to be in desired form, i.e., a (n, m, d,－) function f is in desired form if it is of the form f=f₁‖f₂, where f₁ and f₂ are (n－1,m, d－1,－) functions^[4].

1-2 In Ref.^[20], if Δ_f1,f2(α)=0 for all α∈F₂^n－1, we say that two functions f₁ and f₂ above are perfectly uncorrelated. From the Corollary 3.4 in Ref.^[20], we know that f₁ and f₂ are perfectly uncorrelated if and only if f₁ and f₂ have non-intersecting spectra, i.e.,W_f1(α)W_f2(α)=0 for all α. So, the result in Theorem 1 is equivalent to [4, Proposition 3].

4 GAC of f₁(x)‖f₂(x)‖f₃(x)‖f₄(x)

In this section, we mainly discuss Boolean function

$g(x,{x_{n + 1}},{x_{n + 2}}) = {f_1}\left( x \right)\left\| {{f_2}\left( x \right)} \right\|\left. {{f_3}\left( x \right)} \right\|{f_4}\left( x \right) \in {{\rm B}_{n + 2}}$

(3)

i.e., the algebraic normal form of g(x, x_n+1,x_n+2) is

$\begin{array}{*{20}{l}} {g\left( {x,{x_{n + 1}},{x_{n + 2}}} \right) = {f_1} \oplus {x_{n + 1}}\left( {{f_1} \oplus {f_2}} \right) \oplus {x_{n + 2}}({f_1} \oplus }\\ {{f_3}) \oplus {x_{n + 1}}{x_{n + 2}}\left( {{f_1} \oplus {f_2} \oplus {f_3} \oplus {f_4}} \right)} \end{array}$

where x∈F₂ⁿ,(x_n+1,x_n+2)∈F²₂. We shall first present the following result.

Lemma 2 Let g be defined as formula (3). Then

${\Delta _g}\left( {\alpha ,0,0} \right) = {\Delta _{{f_1}}}\left( \alpha \right) + {\Delta _{{f_2}}}\left( \alpha \right) + {\Delta _{{f_3}}}\left( \alpha \right) + {\Delta _{{f_4}}}\left( \alpha \right)$

(4)

${\Delta _g}\left( {\alpha ,0,1} \right) = 2\left[ {{\Delta _{{f_1},{f_3}}}\left( \alpha \right) + {\Delta _{{f_2},{f_4}}}\left( \alpha \right)} \right]$

(5)

${\Delta _g}\left( {\alpha ,1,0} \right) = 2\left[ {{\Delta _{{f_1},{f_2}}}\left( \alpha \right) + {\Delta _{{f_3},{f_4}}}\left( \alpha \right)} \right]$

(6)

${\Delta _g}\left( {\alpha ,1,1} \right) = 2\left[ {{\Delta _{{f_1},{f_4}}}\left( \alpha \right) + {\Delta _{{f_2},{f_3}}}\left( \alpha \right)} \right]$

(7)

where α∈F₂ⁿ.

Proof We only prove the Eqs.(4) and (5). According to Definition 2, set α∈F₂ⁿ,x_n+1,x_n+2∈F₂, we deduce that

$\begin{align} & {{\Delta }_{g}}\left( \alpha ,0,0 \right)=\sum\limits_{(x,{{x}_{n+1}},{{x}_{n+2}})\in F_{2}^{n+2}}{{{\left( -1 \right)}^{g(x,{{x}_{n+1}},{{x}_{n+2}})\oplus g(x\oplus \alpha ,{{x}_{n+1}},{{x}_{n+2}})}}}= \\ & \sum\limits_{x\in F_{2}^{n}}{{{\left( -1 \right)}^{{{f}_{1}}\left( x \right)\oplus {{f}_{1}}(x\oplus \alpha )}}}+\sum\limits_{x\in F_{2}^{n}}{{{\left( -1 \right)}^{{{f}_{2}}\left( x \right)\oplus {{f}_{2}}(x\oplus \alpha )}}}+ \\ & \sum\limits_{x\in F_{2}^{n}}{{{\left( -1 \right)}^{{{f}_{3}}\left( x \right)\oplus {{f}_{3}}(x\oplus \alpha )}}}+\sum\limits_{x\in F_{2}^{n}}{{{\left( -1 \right)}^{{{f}_{4}}\left( x \right)\oplus {{f}_{4}}(x\oplus \alpha )}}}= \\ & {{\Delta }_{{{f}_{1}}}}\left( \alpha \right)+{{\Delta }_{{{f}_{2}}}}\left( \alpha \right)+{{\Delta }_{{{f}_{3}}}}\left( \alpha \right)+{{\Delta }_{{{f}_{4}}}}\left( \alpha \right) \\ \end{align}$

Now we prove equality (5).

$\begin{align} & {{\Delta }_{g}}\left( \alpha ,0,1 \right)=\sum\limits_{(x,{{x}_{n+1}},{{x}_{n+2}})\in F_{2}^{n+2}}{{{\left( -1 \right)}^{g(x,{{x}_{n+1}},{{x}_{n+2}})\oplus g(x\oplus \alpha ,{{x}_{n+1}},{{x}_{n+2}}\oplus 1)}}}= \\ & \sum\limits_{x\in F_{2}^{n}}{{{\left( -1 \right)}^{{{f}_{1}}\left( x \right)\oplus {{f}_{3}}(x\oplus \alpha )}}}+ \\ & \sum\limits_{x\in F_{2}^{n}}{{{\left( -1 \right)}^{{{f}_{3}}\left( x \right)\oplus {{f}_{1}}(x\oplus \alpha )}}}+ \\ & \sum\limits_{x\in F_{2}^{n}}{{{\left( -1 \right)}^{{{f}_{2}}\left( x \right)\oplus {{f}_{4}}(x\oplus \alpha )}}}+\sum\limits_{x\in F_{2}^{n}}{{{\left( -1 \right)}^{{{f}_{4}}\left( x \right)\oplus {{f}_{2}}(x\oplus \alpha )}}}= \\ & 2\left( {{\Delta }_{{{f}_{1}},{{f}_{3}}}}\left( \alpha \right)+{{\Delta }_{{{f}_{2}},{{f}_{4}}}}\left( \alpha \right) \right). \\ \end{align}$

The proof is completed.

According to Lemma 2, when f₂=f₃, we can get the result in Lemma 3 of Ref.^[21]. By using the result, the sufficient and necessary condition is obtained for constructing a bent function with f₁‖f₂‖f₃‖f₄ in Ref.^[21]. In the following, we study the sum-of-squares indicator of g. We need the following lemma^[22].

Lemma 3^[22] Let f₁(x),f₂(x),f₃(x),f₄(x)∈B_n. Then

$\sum\limits_{\alpha \in F_2^n} {{\Delta _{{f_1},{f_2}}}\left( \alpha \right)} {\Delta _{{f_3},{f_4}}}\left( {\alpha \oplus e} \right) = \sum\limits_{\alpha \in F_2^n} {{\Delta _{{f_1},{f_3}}}\left( a \right)} {\Delta _{{f_2},{f_4}}}\left( {a \oplus e} \right)$

In Lemma 3, if e=0, we have

$\sum\limits_{\alpha \in F_2^n} {{\Delta _{{f_1},{f_2}}}\left( \alpha \right)} {\Delta _{{f_3},{f_4}}}\left( \alpha \right) = \sum\limits_{\alpha \in F_2^n} {{\Delta _{{f_1},{f_3}}}\left( a \right)} {\Delta _{{f_2},{f_4}}}\left( a \right)$

(8)

Theorem 2 Let g be defined as formula (3), then

$\begin{array}{*{20}{c}} {{\sigma _g} = {\sigma _{{f_1}}} + {\sigma _{{f_2}}} + {\sigma _{f3}} + {\sigma _{{f_4}}} + 6({\sigma _{{f_1},{f_2}}} + {\sigma _{{f_1},{f_3}}} + {\sigma _{{f_1},{f_4}}} + }\\ {{\sigma _{{f_2},{f_3}}} + {\sigma _{{f_2},{f_4}}} + {\sigma _{{f_3},{f_4}}}) + 24\lambda } \end{array}$

(9)

where $\lambda = \sum\limits_{\alpha \in F_2^n} {{\Delta _{{f_1},{f_2}}}\left( \alpha \right)} {\Delta _{{f_3},{f_4}}}\left( \alpha \right)$ .

Proof According to the definition of auto-correlation function and Lemmas 2,3, we get

$\begin{array}{*{20}{l}} {{\sigma _g} = \sum\limits_{(a,{a_{n + 1}},{a_{n + 2}}) \in F_2^n \times {F_2} \times {F_2}} {\Delta _g^2(a,{a_{n + 1}},{a_{n + 2}})} = }\\ {\sum\limits_{a \in F_2^n,{a_{n + 1}} = 0,{a_{n + 2}} = 0} {\Delta _g^2\left( {a,0,0} \right)} + \sum\limits_{a \in F_2^n,{a_{n + 1}} = 0,{a_{n + 2}} = 1} {\Delta _g^2\left( {a,0,1} \right) + } }\\ {\sum\limits_{a \in F_2^n,{a_{n + 1}} = 1,{a_{n + 2}} = 0} {\Delta _g^2\left( {a,1,0} \right)} + \sum\limits_{a \in F_2^n,{a_{n + 1}} = 1,{a_{n + 2}} = 1} {\Delta _g^2\left( {a,1,1} \right)} = }\\ {\sum\limits_{a \in F_2^n} {{{\left( {{\Delta _{{f_1}}}\left( a \right) + {\Delta _{{f_2}}}\left( a \right) + {\Delta _{{f_3}}}\left( a \right) + {\Delta _{{f_4}}}\left( a \right)} \right)}^2}} + }\\ {4\sum\limits_{a \in F_2^n} {{{\left( {{\Delta _{{f_1},{f_3}}}\left( a \right) + {\Delta _{{f_2},{f_4}}}\left( a \right)} \right)}^2}} + 4\sum\limits_{a \in F_2^n} {\left( {{\Delta _{{f_1},{f_2}}}\left( a \right)} \right. + } }\\ {{{\left. {{\Delta _{{f_3},{f_4}}}\left( a \right)} \right)}^2} + 4\sum\limits_{a \in F_2^n} {{{\left( {{\Delta _{{f_1},{f_4}}}\left( a \right) + {\Delta _{{f_2},{f_3}}}\left( a \right)} \right)}^2}} = }\\ {\sum\limits_{a \in F_2^n} {\left( {\Delta _{{f_1}}^2\left( a \right) + \Delta _{{f_2}}^2\left( a \right) + \Delta _{{f_3}}^2\left( a \right) + \Delta _{{f_4}}^2\left( a \right)} \right)} + }\\ {2\sum\limits_{a \in F_2^n} {\left( {{\Delta _{{f_1}}}\left( a \right){\Delta _{{f_2}}}\left( a \right) + {\Delta _{{f_1}}}\left( a \right){\Delta _{{f_3}}}\left( a \right) + {\Delta _{{f_1}}}\left( a \right){\Delta _{{f_4}}}\left( a \right)} \right)} + }\\ {2\sum\limits_{a \in F_2^n} {\left( {{\Delta _{{f_2}}}\left( a \right){\Delta _{{f_3}}}\left( a \right) + {\Delta _{{f_2}}}\left( a \right){\Delta _{{f_3}}}\left( a \right) + {\Delta _{{f_3}}}\left( a \right){\Delta _{{f_4}}}\left( a \right)} \right)} + }\\ {4\sum\limits_{a \in F_2^n} {\left( {\Delta _{{f_1},{f_3}}^2\left( a \right) + \Delta _{{f_2},{f_4}}^2\left( a \right)} \right)} + 8\sum\limits_{a \in F_2^n} {{\Delta _{{f_1},{f_3}}}\left( a \right){\Delta _{{f_2},{f_4}}}\left( a \right)} + }\\ {4\sum\limits_{a \in F_2^n} {\left( {\Delta _{{f_1},{f_2}}^2\left( a \right) + \Delta _{{f_3},{f_4}}^2\left( a \right)} \right)} + 8\sum\limits_{a \in F_2^n} {{\Delta _{{f_1},{f_2}}}\left( a \right){\Delta _{{f_3},{f_4}}}\left( a \right)} + }\\ {4\sum\limits_{a \in F_2^n} {\left( {\Delta _{{f_1},{f_4}}^2\left( a \right) + \Delta _{{f_2},{f_3}}^2\left( a \right)} \right)} + 8\sum\limits_{a \in F_2^n} {{\Delta _{{f_1},{f_4}}}\left( a \right){\Delta _{{f_2},{f_3}}}\left( a \right)} + } \end{array}$

$\begin{array}{*{20}{c}} {{\sigma _g} = {\sigma _{{f_1}}} + {\sigma _{{f_2}}} + {\sigma _{f3}} + {\sigma _{{f_4}}} + 6({\sigma _{{f_1},{f_2}}} + {\sigma _{{f_1},{f_3}}} + {\sigma _{{f_1},{f_4}}}}\\ { + {\sigma _{{f_2},{f_3}}} + {\sigma _{{f_2},{f_4}}} + {\sigma _{{f_3},{f_4}}}) + 24\lambda } \end{array}$

where $\lambda = \sum\limits_{\alpha \in F_2^n} {{\Delta _{{f_1},{f_2}}}\left( \alpha \right)} {\Delta _{{f_3},{f_4}}}\left( \alpha \right)$ .

The iterative construction of bent functions for constructing n+2-variable bent functions from n-variable bent functions was proposed in the Corollary 1 of Ref.^[19]. According to Theorem 2, we can easily get this result.

Corollary 1 Let n be even and f(x), g(x)∈B_n be two bent functions, then

$F = f\left( x \right)\left\| {f\left( {x \oplus a} \right)} \right\|\left. {g\left( x \right)} \right\|\left( {g\left( {x + a} \right) \oplus 1} \right)$

is a bent function, where a∈F₂ⁿ.

Proof Thanks to Proposition 1, we deduce from Theorem 2 that

$\begin{array}{*{20}{c}} {{\sigma _{{f_1}}} = {\sigma _{{f_2}}} = {\sigma _f},{\sigma _{{f_3}}} = {\sigma _{{f_4}}} = {\sigma _g},{\sigma _{{f_1},{f_2} = }}{\sigma _f}}\\ {{\sigma _{{f_1},{f_3}}} = {\sigma _{{f_1},{f_4}}} = {\sigma _{{f_2},{f_3}}} = {\sigma _{{f_2},{f_4}}} = {\sigma _{f, g}},{\sigma _{{f_3},{f_4}}} = {\sigma _g}}\\ {{\Delta _{{f_1},{f_2}}}\left( a \right) = {\Delta _f}\left( a \right),{\Delta _{{f_3},{f_4}}}\left( a \right) = - {\Delta _g}\left( a \right),\lambda = - {\sigma _{f, g}}} \end{array}$

Thus,

${\sigma _F} = 2{\sigma _f} + 2{\sigma _g} + 6{\sigma _f} + 24{\sigma _{f, g}} + 6{\sigma _g} - 24{\sigma _{f, g}} = 8{\sigma _f} + 8{\sigma _g}$

as σ_f=σ_g=2²ⁿ, so

${\sigma _F} = 8{\sigma _f} + 8{\sigma _g} = {2^{2n + 4}} = {2^{2(n + 2)}}$

Therefore,F is bent.

Corollary 2 Let f∈B_n, considering the function g∈B_n+2 with

$g = f\left\| f \right\|\left. f \right\|\bar f$

then σ_g=16σ_f.

Proof Using formula (9) and Proposition 1, we have

${\sigma _g} = 4{\sigma _f} + 36{\sigma _f} - 24{\sigma _f} = 16{\sigma _f}$

Remark 2 The function g above was studied in Ref.^[4]. From Ref.^[4], we know that if f is a (n,1, d, x) function, where d≥2, then g is a (n+2,1,d,2ⁿ+2x) function. Moreover, from Corollary 2, we obtain that if f is a bent function, and then σ_f=2²ⁿ, where n is even, and σ_g=16σ_f=16·2²ⁿ=2²⁽ⁿ⁺²⁾. Thus,g is also a bent function.

In the end of this section, we investigate an existing construction method^{[4, 18]} for generating resilient functions on a certain number of variables from functions on a lower number of a variables.

Construction^[18] Let f be a (n, m, d, x) function with f=f₁‖f₂, where f₁,f₂ are both (n－1,m, d－1,－) functions. Let

$F = f\left\| {\bar f} \right\|\left. {\bar f} \right\|f, G = g\left\| h \right\|\left. {\bar h} \right\|\bar g$

where g=f₁‖f₁and h=f₂‖f-₂. Then, the function H=F‖G is a (n+3,m+2,d+1,2ⁿ⁺¹+4x) function.

For the functions F, G^[18] has been shown that the set of nonzero Walsh transforms of the constituent functions of H are disjoint. Thus, according to Ref.^[20], we obtain that Δ_{F, G}(β)=0 or all β∈F₂ⁿ⁺² and σ_{F, G}=0. However, it is not very clear what is the relationship among σ_H,σ_F and σ_G. Next we will study this problem as follows.

Theorem 3 With the same notation as above, we have σ_H=2σ_F=2σ_G.

Proof By using formula (2), we have σ_H=σ_F+σ_G+6σ_{F, G}. Since Δ_{F, G}(β)=0 for all β∈F₂ⁿ⁺² and σ_{F, G}=0. Hence,σ_H=σ_F+σ_G. In the following, we shall compute σ_F,σ_G, respectively.

Step 1 According to formula (9) and Proposition 1, we have

${\sigma _F} = 4{\sigma _f} + 36{\sigma _f} + 24{\sigma _f} = 64{\sigma _f}$

As,σ_f=σ_f1+σ_f1+6σ_f1,f2. Hence,

${\sigma _F} = 64{\sigma _{{f_1}}} + 64{\sigma _{{f_1}}} + 384{\sigma _{{f_1},{f_2}}}$

(10)

Step 2 From formula (9), Proposition 1 and the definition of sum-of-squares indicator, we have

$\begin{array}{l} {\sigma _G} = 2{\sigma _g} + 2{\sigma _h} + 6(4{\sigma _{g, h}} + {\sigma _g} + {\sigma _h}) + 24{\sigma _{g, h}} = \\ 8{\sigma _g} + 8{\sigma _h} + 48{\sigma _{g, h}} \end{array}$

Moreover, fromformula (2) and Proposition 1, we get

${\sigma _g} = 8{\sigma _{{f_1}}},{\sigma _h} = 8{\sigma _{{f_2}}}$

Now we compute σ_{g, h}, by using the definition of auto-correlation function. For any w∈F₂^n－1,w_n∈F₂, we have

${\Delta _g}\left( {w,{w_n}} \right) = \left\{ {\begin{array}{*{20}{l}} {2{\Delta _{{f_1}}}\left( \omega \right),}&{{\rm{if}}{\omega _n} = 0}\\ { - 2{\Delta _{{f_1}}}\left( \omega \right),}&{{\rm{if}}{\omega _n} = 1} \end{array}} \right.$

and

${\Delta _h}\left( {w,{w_n}} \right) = \left\{ {\begin{array}{*{20}{l}} {2{\Delta _{{f_2}}}\left( \omega \right),}&{{\rm{if}}{\omega _n} = 0}\\ { - 2{\Delta _{{f_2}}}\left( \omega \right),}&{{\rm{if}}{\omega _n} = 1} \end{array}} \right.$

Then

$\begin{align} & {{\sigma }_{g, h}}=\sum\limits_{\alpha \in F_{2}^{n}}{\Delta _{g, h}^{2}}\left( \alpha \right)=\sum\limits_{\omega \in F_{2}^{n-1},{{\omega }_{n}}\in {{F}_{2}}}{{{\Delta }_{g}}(\omega ,{{\omega }_{n}}){{\Delta }_{h}}(\omega ,{{\omega }_{n}})}= \\ & \sum\limits_{\omega \in F_{2}^{n-1}}{{{\Delta }_{g}}\left( \omega ,0 \right){{\Delta }_{h}}\left( \omega ,0 \right)}+\sum\limits_{\omega \in F_{2}^{n-1}}{{{\Delta }_{g}}\left( \omega ,1 \right){{\Delta }_{h}}\left( \omega ,1 \right)}= \\ & 4\sum\limits_{\omega \in F_{2}^{n-1}}{{{\Delta }_{{{f}_{1}}}}\left( \omega \right){{\Delta }_{{{f}_{2}}}}\left( \omega \right)}+4\sum\limits_{\omega \in F_{2}^{n-1}}{{{\Delta }_{{{f}_{1}}}}\left( \omega \right){{\Delta }_{{{f}_{2}}}}\left( \omega \right)}= \\ & 8\sum\limits_{\omega \in F_{2}^{n-1}}{{{\Delta }_{{{f}_{1}}}}\left( \omega \right){{\Delta }_{{{f}_{2}}}}\left( \omega \right)}=8{{\sigma }_{{{f}_{1}},{{f}_{2}}}} \\ \end{align}$

Therefore,

${\sigma _G} = 64{\sigma _{{f_1}}} + 64{\sigma _{{f_1}}} + 384{\sigma _{{f_1},{f_2}}}$

(11)

Combining formulas (10) and (11), we have

${\sigma _F} = {\sigma _G}$

Thus,σ_H=2σ_F=2σ_G. This completes the proof.

Remark 3 In Ref.^[11], Zhou et al. claimed that if f=f₁‖f₂, where f₁,f₂∈β_n-1,

Then

${\sigma _{{f_1}}} + {\sigma _{{f_2}}} \le {\sigma _f} \le {\sigma _{{f_1}}} + {\sigma _{{f_2}}}6\sqrt {{\sigma _{{f_1}}}{\sigma _{{f_2}}}} $

where σ_f1+σ_f2=σ_f if and only if Δ_f1,f2(α)=0 for all α∈F₂^n-1. According to Theorem 3, we know that this construction can get a Boolean function with the lower bound on sum-of-squares indicator by choosing the proper initial functions.

5 Conclusions

In this paper, we mainly discuss the GAC of Boolean function by concatenation, i.e.,f₁‖f₂ and f₁‖f₂‖f₃‖f₄. For the function f=f₁‖f₂, we study the cross-correlation function of f₁,f₂ in the special condition. Finally, for the function g=f₁‖f₂‖f₃‖f₄, by analyzing the relation among their auto-correlation functions, we investigate its sum-of-squares indicator. Also, we obtain some interesting results on this function. The future work will focus on how to construct the Boolean functions with good GAC using these results. Furthermore we hope that these results will be considered helpful in further study of Boolean functions.