A systematic method of constructing Boolean functions with optimal algebraic immunity based on the generator matrix of the Reed–Muller code

Abstract

Because of the recent algebraic attacks, optimal algebraic immunity is now an absolutely necessary (but not sufficient) property for Boolean functions used in stream ciphers. In this paper, we firstly determine the concrete coefficients in the linear expression of the column vectors with respect to a given basis of the generator matrix of Reed–Muller code, which is an important tool for constructing Boolean functions with optimal algebraic immunity. Secondly, as applications of the determined coefficients, we provide simpler and direct proofs for two known constructions. Further, we construct new Boolean functions on odd variables with optimal algebraic immunity based on the generator matrix of Reed–Muller code. Most notably, the new constructed functions possess the highest nonlinearity among all the constructions based on the generator matrix of Reed–Muller code, although which is not as good as the nonlinearity of Carlet–Feng function. Besides, the ability of the new constructed functions to resist fast algebraic attacks is also checked for the variable $n=11,13$ and 15.

1 Introduction

In recent years, there has been great interest in designing symmetric key algorithms for secure communication among devices with restrictions on memory, computing power, etc. Boolean functions play a critical role in cryptography, particularly as a main block of symmetric key algorithms. To resist the known attacks, many criteria have been developed for designing Boolean functions. Cryptographic Boolean functions usually should have balancedness, large algebraic degree, and high nonlinearity before 2003. In 2003, Courtois and Meier successfully proposed algebraic attacks on several stream ciphers [10]. As a result, a new criterion called algebraic immunity [22], the minimum algebraic degree of the nonzero annihilators of $f$ or $f+1$, was imposed on cryptographic Boolean functions. It was shown in [10] that the optimal algebraic immunity of an $n$-variable Boolean function is $\lceil {n\over 2}\rceil$. The construction of Boolean functions with optimal algebraic immunity is obviously of great importance and therefore attracts a lot of attention [7, 11–13, 17]. Later, fast algebraic attack [9] was introduced by Courtois. The fast algebraic attack on a Boolean function $f$ is feasible if there exists a function $g$ of small degree such that the multiple $gf$ has degree not too large. Another important characteristic for designing Boolean functions is good nonlinearity which measures the ability of the functions to resist fast correlation attacks [21].

Among the known Boolean functions with optimal algebraic immunity, the simplest one is the so-called majority function

$$\begin{aligned} F(x)=\left\{ \begin{array}{ll}1,&\mathrm{wt}(x)\ge \lceil \frac{n}{2}\rceil \\ 0,&\mathrm{otherwise}\end{array}\right. \end{aligned}$$

which was firstly proposed by Ding et al. [15]. In 2006, Dalai et al. [14] showed that the majority function $F(x)$ achieves the optimal algebraic immunity. However, the nonlinearity of majority function is $2^{n-1}-\big (_{\lfloor {n\over 2}\rfloor }^{n-1}\big )$, which is almost the worst possible value according to Lobanov’s bound [20].

In 2005, Carlet et al. pointed out an interesting connection between the Boolean functions with optimal algebraic immunity and the Reed–Muller codes [6]. They presented a sufficient and necessary condition for constructing Boolean functions with optimal algebraic immunity based on the generator matrix of Reed–Muller code. Later, in 2007, Carlet [3] introduced a general method for constructing balanced Boolean functions on odd number of variables with optimal algebraic immunity, which can be viewed as a modification of the majority function. From then on, following this idea, many modifications of majority function have been proposed to improve its nonlinearity [4, 8, 16, 19, 24, 25]. But, unfortunately the enhanced values are not too much.

In this paper, we explore the linear relationship of the column vectors in the generator matrix of Reed–Muller code. Mainly, we can give a systematic method of constructing Boolean functions with optimal algebraic immunity based on the generator matrix of Reed–Muller code. As an application, we are able to construct new Boolean functions with optimal algebraic immunity and highest nonlinearity among all the constructions based on the generator matrix of Reed–Muller code.

The paper is organized as follows. In Sect. 2, some preliminaries about the $n$-variable Boolean functions, the $k$th order Reed–Muller code $\text{ RM}(k,n)$ and its generator matrix $G(k,n)$ are reviewed. In Sect. 3, the linear expression of the column vectors in the generator matrix of $\text{ RM}(k,n)$ is established. In Sect. 4, a general method for constructing Boolean functions with optimal algebraic immunity is presented based on the determined linear expression. As applications, some known constructions are re-explained, and a new construction of Boolean functions with optimal algebraic immunity and high nonlinearity is presented as well. Finally, Sect. 5 concludes the paper.

2 Preliminaries

Let $\mathbb F _2^n$ be the $n$-dimensional vector space over the finite field $\mathbb F _2=\{0,1\}$. Given a vector $\alpha =(a_1,a_2,\ldots ,a_n)\in \mathbb F _2^n$, we define its support $\mathrm{supp}(\alpha )$ as the set $\{1\le i\le n \,|\,a_i=1 \}$, and its Hamming weight $\mathrm{wt}(\alpha )$ as the cardinality of its support, i.e., $\mathrm{wt}(\alpha )=|\mathrm{supp}(\alpha )|$.

For any two vectors $\alpha =(a_1,a_2,\ldots ,a_n)$ and $\beta =(b_1,b_2,\ldots ,b_n)\in \mathbb F _2^n,\,\alpha$ is said to be covered by $\beta$ if $a_i \le b_i$ for all $1\le i\le n$. For short, written as $\alpha \preceq \beta$. In this paper, we define $\beta ^\alpha =b_1^{a_1}b_2^{a_2}\cdots b_n^{a_n}$ with $0^0=1^1=1^0=1$ and $0^1=0$. Obviously,

$$\begin{aligned} \beta ^\alpha =1 \mathrm{~if~ and~ only ~if~} \alpha \preceq \beta . \end{aligned}$$

(1)

A Boolean function on $n$ variables is a mapping from $\mathbb F _2^n$ into $\mathbb F _2$. We denote by $\mathcal B _n$ the set of all $n$-variable Boolean functions. In cryptography, the most usual representation of a function $f\in \mathcal B _n$ is the algebraic normal form (ANF) as follows

$$\begin{aligned} f(x)=\bigoplus \limits _{\alpha \in \mathbb F _2^n}c(\alpha )x^\alpha \end{aligned}$$

(2)

where $c(\alpha )\in \mathbb F _2$.

For a function $f\in \mathcal B _n$, the support of $f$ is $\mathrm{supp}(f)=\{\alpha \in \mathbb F _2^n|f(\alpha ) = 1\}$. By convenience, define $\mathrm{zeros}(f)=\{\alpha \in \mathbb F _2^n|f(\alpha ) = 0\}$ as well. The Hamming weight of $f,\,\mathrm{wt}(f)$, is the cardinality of its support. We say that a Boolean function $f$ is balanced if $\mathrm{wt}(f)=2^{n-1}$. The Hamming distance between $f$ and $g\in \mathcal B _n$ is $d_H(f,g)=\mathrm{wt}(f\oplus g)$. The algebraic degree of a Boolean function $f$ in (2) is defined as

$$\begin{aligned} \mathrm{deg}(f)=\max \{\mathrm{wt}(\alpha )\,|\, c(\alpha )=1\}. \end{aligned}$$

If $\mathrm{deg}(f)\le 1$, then $f$ is called an affine function.

Definition 1

([22]) For an $n$-variable Boolean function $f$, define $AN(f) = \{g\in \mathcal B _n| fg=0\}$. A Boolean function $g\in AN(f)$ is called an annihilator of $f$. The algebraic immunity $(AI)$ of an $n$-variable Boolean function $f$, denoted by $AI(f)$, is defined as $AI(f)=\min \{\mathrm{deg}(g)|g\ne 0~ \mathrm{such\,that}~ fg=0~\mathrm{or}~(f+1)g=0\}$.

In this paper, an $n$-variable Boolean function $f$ is said to have optimal AI if $AI(f)=\lceil \frac{n}{2}\rceil$ (see [10]). A high algebraic immunity is necessary but not sufficient condition for resistance against all kinds of algebraic attacks. If one can find $g$ of low degree and $h\ne 0$ of reasonable degree such that $fg=h$, then a fast algebraic attack is feasible [1, 9, 18]. An $n$-variable Boolean function can be considered as optimal with respect to fast algebraic attacks if there do not exist two nonzero functions $g$ and $h$ such that $fg=h$ and $\mathrm{deg}(g)+\mathrm{deg}(h)<n$ with $\mathrm{deg}(g)<\frac{n}{2}$.

Walsh spectrum is an important tool for studying Boolean functions. The Walsh spectrum of an $n$-variable Boolean function $f$ is a integer-valued function over $\mathbb F _2^n$ defined as

$$\begin{aligned} W_f(\omega )=\sum \limits _{x\in \mathbb F _2^n}(-1)^{f(x)\oplus x\cdot \omega } \end{aligned}$$

(3)

where $x\cdot \omega =x_1a_1\oplus x_2a_2\oplus \cdots \oplus x_na_n$ for $x=(x_1,x_2,\ldots ,x_n)$ and $\omega =(a_1,a_2,\ldots ,a_n)\in \mathbb F _2^n$. The nonlinearity of $f$ is the minimum Hamming distance between $f$ and all affine functions, which can be expressed according to Walsh spectrum as

$$\begin{aligned} nl_f=2^{n-1}-{1\over 2}\max \limits _{\omega \in \mathbb F _2^n}|W_f(\omega )|. \end{aligned}$$

(4)

Throughout this paper, assume that $\alpha _1,\alpha _2,\ldots , \alpha _{2^n}$ are all the $2^n$ vectors in $\mathbb F _2^n$, which are ordered according to the Hamming weight firstly and the lexicographic order secondly, i.e., $\alpha _1=(0,0,0,\ldots ,0),\,\alpha _2=(1,0,0,\ldots ,0),\,\alpha _3 =(0,1,0,\ldots ,0),\,\ldots ,\, \alpha _{n+1}=(0,0,0,\ldots ,0,1),\,\alpha _{n+2} =(1,1,0,\ldots ,0),\,\alpha _{n+3}=(1,0,1,0,\ldots ,0),\,\alpha _{n+4} =(1,0,0,1, \ldots ,0),\,\ldots ,\, \alpha _{{n\atopwithdelims ()2}+n+1}=(0,\ldots ,0,1,1),\,\ldots ,\, \alpha _{2^n}=(1,1,1,\ldots ,1)$. Then, it is easy to see that $\mathrm{wt}(\alpha _i)\le k$ if and only if $1\le i \le \sum _{j=0}^k{n\atopwithdelims ()j}$. Hence, the ANF of a Boolean function $f$ with $\mathrm{deg}(f)\le k$ can be expressed as

$$\begin{aligned} f(x)=\bigoplus \limits _{i=1}^{s}c(\alpha _i)x^{\alpha _i} \end{aligned}$$

(5)

where $s=\sum _{i=0}^k{n\atopwithdelims ()i}$ and $c(\alpha _i)\in \mathbb F _2$, since $\mathrm{deg}(x^{\alpha _i})\le k$ if and only if $\mathrm{wt}(\alpha _i)\le k$.

The truth table is another representation of a Boolean function. In this paper, for convenience, the truth table of a Boolean function $f$ is of the following form

$$\begin{aligned} f=[f(\alpha _1),f(\alpha _2),\ldots ,f(\alpha _{2^n})]. \end{aligned}$$

Reed–Muller codes are amongst the oldest and most popular codes. They were discovered by Muller and Reed in 1954 [23, 26]. The Reed–Muller code of order $k,\,1\le k\le n$, is by definition the set of all $n$-variable Boolean functions with algebraic degrees at most $k$, denoted by $\text{ RM}(k,n)$. Clearly, it is a vector space of dimension $\sum _{i=0}^k{n\atopwithdelims ()i}$ over $\mathbb F _2$, with monomials of degrees at most $k$, i.e., $\Big \{x^{\alpha _i}\Big | 1\le i \le \sum _{j=0}^k{n\atopwithdelims ()j}\Big \}$, denoted by $\varGamma _k$, as its basis.

Define a mapping $\psi :\varGamma _k\rightarrow \mathbb F _2^{2^n}$

$$\begin{aligned} \psi (x^{\alpha _i})=\left[{\alpha _1}^{\alpha _i}, {\alpha _2}^{\alpha _i},\ldots ,{\alpha _{2^n}}^{\alpha _i}\right] \end{aligned}$$

which is the truth table of $x^{\alpha _i}$, for $1\le i \le \sum _{j=0}^k{n\atopwithdelims ()j}$. Consider the following $\sum _{i=0}^k{n\atopwithdelims ()i}\times 2^n$ matrix as

$$\begin{aligned} G(k,n)= \left(\begin{array}{c}\psi (x^{\alpha _1})\\ \psi (x^{\alpha _2})\\ \vdots \\ \psi (x^{\alpha _s})\end{array}\right)= \left(\begin{array}{cccccccccccccccc} {\alpha _1}^{\alpha _1}&{\alpha _2}^{\alpha _1}&\cdots&{\alpha _{2^n}}^{\alpha _{1}}\\ {\alpha _1}^{\alpha _2}&{\alpha _2}^{\alpha _2}&\cdots&{\alpha _{2^n}}^{\alpha _2}\\ \vdots&\vdots&\,&\vdots \\ {\alpha _1}^{\alpha _s}&{\alpha _2}^{\alpha _s}&\cdots&{\alpha _{2^n}}^{\alpha _s}\\ \end{array}\right) \end{aligned}$$

(6)

where $s=\sum _{i=0}^k{n\atopwithdelims ()i}$. Note that if $k=\lceil \frac{n}{2}\rceil -1$ then $\sum _{i=0}^k{n\atopwithdelims ()i}$ equals $2^{n-1}$ when $n$ is odd, and $2^{n-1}-{n-1\atopwithdelims ()\frac{n}{2}}$ otherwise. By means of the matrix $G(k,n)$, it is easy to check that any function $f\in \mathcal B _n$ with $\mathrm{deg}(f)\le k$, given by (5), can be expressed as follows

$$\begin{aligned}{}[f(\alpha _1), \ldots ,f(\alpha _{2^n})]=[c(\alpha _1), \ldots ,c(\alpha _s)]G(k,n). \end{aligned}$$

That is, $G(k,n)$ is a generator matrix of the Reed–Muller code $\text{ RM}(k, n)$.

For instance, when $n=3$, the vectors in $\mathbb F _2^3$ are $\alpha _1=(0,0,0),\,\alpha _2=(1,0,0),\,\alpha _3=(0,1,0),\,\alpha _4 =(0,0,1),\,\alpha _5=(1,1,0),\,\alpha _6=(1,0,1),\,\alpha _7 =(0,1,1),\,\alpha _8=(1,1,1)$. By (1) and (6), the generator matrix of the Reed–Muller code RM(1, 3) is

$$\begin{aligned} G(1,3)=\left(\begin{array}{cccccccccccccccc} 1&1&1&1&1&1&1&1\\ 0&1&0&0&1&1&0&1\\ 0&0&1&0&1&0&1&1\\ 0&0&0&1&0&1&1&1 \end{array}\right). \end{aligned}$$

Throughout this paper, given an $n$-variable Boolean function $f$ and a positive integer $k\le n$, we denote by $G$ the generator matrix $G(k,n)$ of the $k$th order Reed–Muller code $\text{ RM}(k,n)$, and denote by $R_f^{(1)}(k,n)$ (resp. $R_f^{(0)}(k,n)$) the submatrix of $G$ consisting of all the $i$th column vectors in $G,\,1\le i\le 2^n$, such that $\alpha _i\in \mathrm{supp}(f)$ (resp. $\alpha _i\in \mathrm{zeros}(f)$). It is easily seen that the matrix $R_f^{(1)}(k,n)$ (resp. $R_f^{(0)}(k,n)$) has $\sum _{i=0}^k{n\atopwithdelims ()i}$ rows and $\mathrm{wt}(f)$ (resp. $2^n-\mathrm{wt}(f)$) columns.

Concerning a function $f\in \mathcal B _n$ with optimal AI, we have following sufficient and necessary conditions.

Proposition 1

([2, 6]) Let $k= \lceil \frac{n}{2}\rceil -1$. A function $f\in \mathcal B _n$ with $\mathrm{wt}(f)=\sum _{i=0}^k{n\atopwithdelims ()i}$ (resp. $\mathrm{wt}(f)=2^n-\sum _{i=0}^k{n\atopwithdelims ()i}$) has optimal AI if and only if the $\sum _{i=0}^k{n\atopwithdelims ()i}\times \sum _{i=0}^k{n\atopwithdelims ()i}$ matrix $R_f^{(1)}(k,n)$ (resp. $R_f^{(0)}(k,n)$) is nonsingular.

Finally, it should be noted that in this paper for simplicity we do not distinguish the vector $Y=(y_1,\ldots ,y_n)\in \mathbb F _2^n$ and the integer $y=\sum _{i=1}^n y_i 2^{i-1}$ if the context is clear, since they are one-to-one corresponding. Then, we can similarly define $x\preceq y$ for two integers $x,y\in \{0,1,\ldots ,2^n-1\}$ and $X\le Y$ for two vectors $X,Y\in \mathbb F _2^n$.

3 The linear expression of the column vectors in $G$

From now on, we always assume $k= \lceil \frac{n}{2}\rceil -1$ and $s=\sum _{i=0}^k{n\atopwithdelims ()i}$ in this paper.

By (6), we know that the $j$th column vector in the generator matrix $G$ can be expressed as $({\alpha _j}^{\alpha _1},{\alpha _j}^{\alpha _2}, \ldots ,{\alpha _j}^{\alpha _{s}})^T,\,1\le j\le 2^n$. For simplicity, we will always use the notation $c_{\alpha _j}$ to denote the $j$th column vector in $G$, i.e.

$$\begin{aligned} c_{\alpha _j}=({\alpha _j}^{\alpha _1},{\alpha _j}^{\alpha _2}, \ldots ,{\alpha _j}^{\alpha _{s}})^T. \end{aligned}$$

Thus, the generator matrix $G$ in (6) can be written as

$$\begin{aligned} G=(c_{\alpha _1},c_{\alpha _2},\ldots ,c_{\alpha _{2^n}}). \end{aligned}$$

In order to find a function $f\in \mathcal B _n$ with $\mathrm{wt}(f)=s$ and optimal AI, by Proposition 1, it is necessary to get a submatrix $R_f^{(1)}(k,n)$ of $G$ with rank $s$. In this section, we will explore the linear expression of the column vectors in $G$ with respect to this basis $(c_{\alpha _1},c_{\alpha _2},\ldots ,c_{\alpha _{s}})$, which is very useful to check whether the new submatrix of $G$ is of rank $s$.

Theorem 1

For any vector $u\in \mathbb F _2^n$, such that $\mathrm{wt}(u)=k+j,\, 1\le j\le n-k$, we have

$$\begin{aligned} c_u= \bigoplus \limits _{i=0}^k a_i^{(j)}\left({\mathop {\mathop {\bigoplus \limits _{\alpha \preceq u}}\limits _{\text{ wt}(\alpha )=k-i}}}c_\alpha \right) \end{aligned}$$

(7)

where $a_i^{(j)}\in \mathbb F _2,\,0\le i\le k$, which satisfies

$$\begin{aligned} a_0^{(j)}=1~\text{ and}~a_i^{(j)}=1 \oplus \bigoplus \limits _{l=0}^{i-1}a_l^{(j)}{{i+j}\atopwithdelims ()i-l},~1\le i\le k. \end{aligned}$$

(8)

Proof

Partition the matrix $G$ in (6) into block matrix as $G=(G_{il})_{(k+1)\times (n+1)}$, where $G_{il}$ is a ${n\atopwithdelims ()i}\times {n\atopwithdelims ()l}$ matrix, $0\le i\le k,0\le l\le n$. By (6), we know that each entry in $G_{il}$ can be expressed as $\beta ^\alpha$ for some $\alpha ,\beta \in \mathbb F _2^n$ with $\mathrm{wt}(\alpha )=i$ and $\mathrm{wt}(\beta )=l$. If $i>l$, straightforwardly $\alpha \not \preceq \beta$, which follows from (1) that $\beta ^\alpha =0$. Then, $G_{il}$ is a zero matrix for $0\le l<i\le k$. If $i= l$, it is easy to see that $\beta ^\alpha =1$ if and only if $\alpha =\beta$ by (1), which implies $G_{ii}$ is an identity matrix for $0\le i\le k$. Therefore, $G$ has the following form

$$\begin{aligned} G=\left(\begin{array}{cccccccccccccccc} I_{d_0}&*&\cdots&*&*&\cdots&\cdots&* \\ 0&I_{d_1}&\ddots&\vdots&\vdots&\,&\vdots \\ \vdots&\ddots&\ddots&*&\vdots&\,&\vdots \\ 0&\cdots&0&I_{d_k}&*&\cdots&\cdots&* \end{array}\right) \end{aligned}$$

(9)

where $I_{d_i}$ is an identity matrix of order $d_i={n\atopwithdelims ()i}$ for $0 \le i \le k$, which indicates that the first $s$ column vectors $c_{\alpha _1},c_{\alpha _2},\ldots ,c_{\alpha _{s}}$ are linearly independent and then form a basis of $\mathbb F _2^s$.

Assume that the linear expression of $c_u$ with $\mathrm{wt}(u)=k+j$ is

$$\begin{aligned} c_u =\bigoplus \limits _{0\le \mathrm{wt}(\alpha )\le k}a(\alpha )c_\alpha =\bigoplus \limits _{i=1}^{s}a(\alpha _i)c_{\alpha _i} \end{aligned}$$

(10)

where $a(\alpha _i)\in \mathbb F _2,\,1\le i\le s$. According to (6) and (9), we know (10) can be rewritten as

$$\begin{aligned} \left(\begin{array}{cccccccccccccccc} I_{d_0}&*&\cdots&* \\ 0&I_{d_1}&\ddots&\vdots \\ \vdots&\ddots&\ddots&* \\ 0&\cdots&0&I_{d_k} \end{array}\right) \left(\begin{array}{cccccccccccccccc} a(\alpha _1) \\ a(\alpha _2)\\ \vdots \\ a(\alpha _{s}) \end{array}\right)= \left(\begin{array}{cccccccccccccccc} u^{\alpha _1} \\ u^{\alpha _2} \\ \vdots \\ u^{\alpha _{s}} \end{array}\right). \end{aligned}$$

(11)

In what follows, we make use of mathematical induction on $i,\,0\le i\le k$, to prove that the coefficients $a(\alpha )$’s in (10) satisfy

• I. $a(\alpha )=0$ for all $\alpha \not \preceq u$;

• II. $a(\alpha )=a(\beta )$ for all $\alpha ,\beta \preceq u$ with $\mathrm{wt}(\alpha )=\mathrm{wt}(\beta ),$

where $\mathrm{wt}(\alpha )=k-i$.

When $i=0$, we get by (11)

$$\begin{aligned} I_{d_k}\left(\begin{array}{c} a(\alpha _t) \\ \vdots \\ a(\alpha _s) \end{array}\right)=\left(\begin{array}{c} u^{\alpha _t} \\ \vdots \\ u^{\alpha _s} \end{array}\right) \end{aligned}$$

where $t=\sum _{l=0}^{k-1}{n\atopwithdelims ()l}+1$. Note that $\mathrm{wt}(\alpha _l)=k$ for $t\le l\le s$. Hence,

$$\begin{aligned} a(\alpha )=u^{\alpha }=\left\{ \begin{array}{ccc} 1,&\alpha \preceq u \\ 0,&\alpha \not \preceq u \end{array}\right. \end{aligned}$$

for $\mathrm{wt}(\alpha )=k$, which gives $a_0^{(j)}=1$. Hence, I and II hold for $i=0$.

Suppose that the assertions I and II hold for all $k-i+1\le \mathrm{wt}(\alpha )\le k$ for some fixed $1\le i\le k$. Denote the coefficients $a(\alpha )$ with $\alpha \preceq u$ and $\mathrm{wt}(\alpha )=k-l$ by $a_{l}^{(j)},\,0\le l\le i-1$. Substituting $a_l^{(j)}$ into (11), we have

$$\begin{aligned}\left(\begin{array}{cccccccccccccccc} I_{d_0}&\,&* \\&\ddots&\\ 0&\,&I_{d_{k-i}}\\ 0&\cdots&0\\ \vdots&\,&\vdots \\ 0&\cdots&0 \end{array}\right) \left(\begin{array}{cccccccccccccccc} a(\alpha _1) \\ \vdots \\ \vdots \\ a(\alpha _{m }) \end{array}\right)=c_u\oplus \bigoplus \limits _{l=0}^{i-1}\left({\mathop {\mathop {\bigoplus \limits _{v\preceq u}} \limits _{\text{ wt}(v)=k-l}}} a_l^{(j)}c_v\right) \end{aligned}$$

where $m=\sum _{l=0}^{k-i}{n\atopwithdelims ()l}$. For any $\alpha$ with $\mathrm{wt}(\alpha )=k-i$, similarly to the case of $i=0$, we can easily get

$$\begin{aligned} a(\alpha )=u^\alpha \oplus \bigoplus \limits _{l=0}^{i-1}\left({\mathop {\mathop {\bigoplus \limits _{v\preceq u}} \limits _{\text{ wt}(v)=k-l}}}a_l^{(j)}v^\alpha \right). \end{aligned}$$

If $\alpha \not \preceq u$, immediately $u^\alpha =0$ and $\alpha \not \preceq v$ (i.e., $v^\alpha =0$) for any $v\preceq u$, which implies that $a(\alpha )=0$. If $\alpha \preceq u$, we know that $u^\alpha =1$ and the number of the vectors $v\in \mathbb F _2^n$, satisfying $\alpha \preceq v\preceq u$ and $\mathrm{wt}(v)=k-l$ for $0\le l\le i-1$, is ${i+j\atopwithdelims ()i-l}$, where $\mathrm{wt}(u)=k+j$. As a result,

$$\begin{aligned} a(\alpha )=1\oplus \bigoplus _{l=0}^{i-1}a_l^{(j)}{{i+j}\atopwithdelims ()i-l} \end{aligned}$$

for any $\alpha \preceq u$ with $\mathrm{wt}(\alpha )=k-i$. This finishes the proof. $\Box$

Further, we can determine the exact value of the coefficient $a_i^{(j)}$ in (7) based on the well-known combinatorial formula (Pascal’s Formula) as

$$\begin{aligned} {m\atopwithdelims ()p}+{m\atopwithdelims ()p+1}={m+1\atopwithdelims ()p+1}. \end{aligned}$$

Theorem 2

For $1\le j \le n-k$, let $u$ be a vector in $\mathbb F _2^n$ with $\mathrm{wt}(u)=k+j.$ In the linear expression of $c_{u}$ in (7), the coefficients $a_i^{(j)}$ of $c_\alpha$ with $\alpha \preceq u$ and $\mathrm{wt}(\alpha )=k-i$ satisfy

$$\begin{aligned} a_i^{(j)}={i+j-1\atopwithdelims ()i}\,(\mathrm{mod}\,2) \end{aligned}$$

(12)

for $0\le i\le k$ and $1\le j\le n-k$.

Proof

We use mathematical induction on $j$ and $i$ to prove (12).

When $j=1$, it is known that $a_0^{(1)}=1$ by (8). Assume that $a_1^{(1)}=\cdots =a_{i-1}^{(1)}=1$, then by (8) we have

$$\begin{aligned} a_i^{(1)}=1\oplus \bigoplus _{l=0}^{i-1}{{i+1}\atopwithdelims ()i-l} =2^{i+1}-1=1\,(\mathrm{mod}\,2). \end{aligned}$$

In other words, we have proved (12) holds for $j=1$.

Suppose that $a_i^{(j-1)}={i+j-2\atopwithdelims ()i}\,(\mathrm{mod}\,2)$ for $0\le i\le k$. As for $j$, we know $a_0^{(j)}=1={j-1\atopwithdelims ()0}$. Assuming that (12) holds up to $i-1$, then by (8) we know

$$\begin{aligned} \begin{array}{rll}a_{i}^{(j)}&= 1\oplus \bigoplus \limits _{l=0}^{i-1}{l+j-1\atopwithdelims ()l}{{i+j}\atopwithdelims ()i-l}\\&= 1\oplus \bigoplus \limits _{l=0}^{i-1}{l+j-1\atopwithdelims ()l}\Big [{{i+j-1}\atopwithdelims ()i-l}\oplus {{i+j-1}\atopwithdelims ()i-l-1}\Big ]\\&= 1\oplus \Big [{{i+j-1}\atopwithdelims ()i}\oplus \bigoplus \limits _{l=1}^{i-1}{l+j-1\atopwithdelims ()l}{{i+j-1}\atopwithdelims ()i-l}\Big ]\oplus \Big [ \bigoplus \limits _{l=0}^{i-2}{l+j-1\atopwithdelims ()l}{{i+j-1}\atopwithdelims ()i-l-1}\oplus {{i+j-2}\atopwithdelims ()i-1}\Big ]\\&= 1\oplus {{i+j-1}\atopwithdelims ()i}\oplus \bigoplus \limits _{l=1}^{i-1}\Big [{l+j-1\atopwithdelims ()l}\oplus {l+j-2\atopwithdelims ()l-1}\Big ]{{i+j-1}\atopwithdelims ()i-l}\oplus {{i+j-2}\atopwithdelims ()i-1}\\&= 1\oplus {{i+j-1}\atopwithdelims ()i}\oplus \bigoplus \limits _{l=1}^{i-1}{l+j-2\atopwithdelims ()l}{{i+j-1}\atopwithdelims ()i-l}\oplus {{i+j-2}\atopwithdelims ()i-1}\\&= 1\oplus \bigoplus \limits _{l=0}^{i-1}{l+j-2\atopwithdelims ()l}{{i+j-1}\atopwithdelims ()i-l}\oplus {{i+j-2}\atopwithdelims ()i-1}\\&= {i+j-2\atopwithdelims ()i}+{i+j-2\atopwithdelims ()i-1}\\&= {i+j-1\atopwithdelims ()i}\,(\mathrm{mod}\,2) \end{array} \end{aligned}$$

where we apply Pascal’s Formula to the second identity, the fifth identity, and the eighth identity respectively, and in the seventh identity we use

$$\begin{aligned} a_i^{(j-1)}=1 \oplus \bigoplus \limits _{l=0}^{i-1}a_l^{(j-1)}{{i+j-1}\atopwithdelims ()i-l}\ \end{aligned}$$

from (8) and the assumption that (12) is valid for $j-1$.

This finishes the proof. $\Box$

4 The applications

In the remainder of this paper, for simplicity we denote $W^{\le i}=\{\alpha \in \mathbb F _2^n| \mathrm{wt}(\alpha )\le i\},\,W^{\ge i}=\{\alpha \in \mathbb F _2^n| \mathrm{wt}(\alpha )\ge i\}$, and $W^{i}=\{\alpha \in \mathbb F _2^n| \mathrm{wt}(\alpha )= i\}$, for $0\le i\le n$.

By Proposition 1, constructing an $n$-variable Boolean function $f$ with $\mathrm{wt}(f)=s$ and optimal AI is equivalent to find out a nonsingular $s\times s$ submatrix of the generator matrix $G$ given in (6). For example, $[c_{\alpha _1},\ldots , c_{\alpha _s}]$ is such a submatrix. Naturally, a general approach is to modify it and then get another nonsingular one. More precisely, for an integer $1\le l \le s$, choose two vector subsets $U=\{u_1,\ldots ,u_l\}\subseteq W^{\ge k+1}$ and $T=\{\beta _1,\ldots ,\beta _l\}\subseteq W^{\le {k}}$. Set $W^{\le k}\setminus T=\{\gamma _1,\ldots ,\gamma _{s-l}\}$. Then, based on the basis $\{c_{\beta _1},\ldots ,c_{\beta _l},c_{\gamma _1},\ldots , c_{\gamma _{s-l}}\}$, the submatrix $[c_{u_1},\ldots ,c_{u_l},c_{\gamma _1},\ldots ,c_{\gamma _{s-l}}]$ can be expressed as

$$\begin{aligned}{}[c_{u_1},\ldots ,c_{u_l},c_{\gamma _1},\ldots ,c_{\gamma _{s-l}}] =[c_{\beta _1},\ldots ,c_{\beta _l},c_{\gamma _1},\ldots ,c_{\gamma _{s-l}}] \left(\begin{array}{cc} B&\mathbf 0 \\ C&I \end{array}\right) \end{aligned}$$

(13)

where $B=(b_{i,j})$ is an ${l\times l}$ matrix, $\mathbf 0$ is a zero matrix, and $I$ is an identity matrix of order $s-l$. Therefore, the key is to select the two vector subsets $U$ and $T$ such that $B$ is nonsingular.

Generally speaking, it is not easy to determine the rank of $B$. However, if $B$ is an upper triangular matrix or a lower triangular matrix, it becomes much easier. Then, the crucial task is to properly choose two vector subsets $U=\{u_1,\ldots ,u_l\}\subseteq W^{\ge k+1}$ and $T=\{\beta _1,\ldots ,\beta _l\}\subseteq W^{\le {k}}$, satisfying the following two conditions C1 and C2.

• C1. The coefficient of $c_{\beta _i}$ in the linear expression of $c_{u_i}$ is $1$, i.e., $b_{i,i}=1$ for $1\le i \le l$;

• C2. The coefficient of $c_{\beta _i}$ in the linear expression of $c_{u_j}$ is $0$, i.e., $b_{i,j}=0$ for all $1\le j<i \le l$, (or for all $1\le i<j \le l$).

In the sequel, we show that Theorem 2 is a powerful tool to check C1 and C2. It not only provides simpler and direct proofs for the known constructions, but also gives a new construction of Boolean functions with optimal AI and high nonlinearity.

4.1 Example 1: The construction given by Carlet in [3]

In [3], Carlet introduced a general way for constructing Boolean functions with optimal AI, which can be regarded as the application of C1 and C2.

Proposition 2

([3]) Let $n$ be odd. For any integer $1\le l \le {n\atopwithdelims ()k}$, choose two sets $U=\{u_1,\ldots ,u_l\}\subseteq W^{k+1}$ and $T=\{\beta _1,\ldots ,\beta _l\}\subseteq W^{\le {k}}$ such that $\beta _i\preceq u_i$ for $1\le i\le l$ and $\beta _i\not \preceq u_j$ for $1\le j<i \le l$. Then, the function $f\in \mathcal B _n$ with $\mathrm{supp}(f)=\left(W^{\le k}\backslash T\right)\cup U$ has optimal AI.

Proof

For $1\le i\le l$, assuming $\mathrm{wt}(\beta _i)=k-i^{\prime }$ for some $i^{\prime }\ge 0$. Since $\beta _i\preceq u_i$ and $\mathrm{wt}(u_i)=k+1$, it follows from Theorem 2 that

$$\begin{aligned} b_{i,i}= a_{i^{\prime }}^{(1)}= {i^{\prime }+1-1\atopwithdelims ()i^{\prime }}=1. \end{aligned}$$

When $1\le j<i \le l,\,b_{i,j}=0$ by Theorem 1 because of $\beta _i\not \preceq u_j$. This finishes the proof. $\Box$

4.2 Example 2: The construction given by Dong et al. in [16]

Later in [16], Dong et al. presented the following construction, which can be viewed as the application of C1 and C2 as well.

Proposition 3

([16]) Let $n$ be odd. For any two vectors $Y_1, Y_2\in \mathbb F _2^n$, define $[Y_1,Y_2)=\{Y\in \mathbb F _2^n | Y_1\le Y<Y_2\}$. Let $Y_1, Y_2, \ldots , Y_s$ be all the $s$ vectors in $W^{\le k}$ sorted by the order that $Y_i<Y_{i+1}$ for $1\le i\le s-1$. Choose vector $X_i \in [Y_i,Y_{i+1})$ for $1\le i \le s-1$ and $X_s$ with $Y_s\preceq X_s$. Let $f$ be the Boolean function defined by $\mathrm{supp}(f)=\bigcup _{i=1}^s \{X_i\}$. Then $f$ has optimal AI.

Proof

For $1\le i \le s-1$, it is easy to verify that

• I. if $\mathrm{wt}(Y_i)<k$ then $Y_{i+1}=Y_i+1$, which implies $X_i=Y_i$;

• II. if $\mathrm{wt}(Y_i)=k$ then $Y_{i+1}=Y_i+2^{j_1}$, where $Y_i=\sum _{l=1}^k 2^{j_l}$ with $0\le j_1<\cdots <j_k\le n-1$. Then, $X_{i}=Y_{i}$, or $Y_i<X_i<Y_{i+1}$ with $\mathrm{wt}(X_i)>k$, which both satisfy $Y_i\preceq X_i$.

Clearly, by the terminologies of $U$ and $T$ above, we have that $U=\{X_i|\mathrm{wt}(Y_i)=k,\mathrm{wt}(X_i)>k\}$ and $T=\{Y_i|\mathrm{wt}(Y_i)=k,\mathrm{wt}(X_i)>k\}$. From Case II, we see that $X_i<Y_{i+1}\le Y_j$ when $i<j$, which implies $Y_j\not \preceq X_i$ and then $b_{i,j}=0$ by Theorem 1. When $i=j$, since $Y_i\preceq X_i$ indicated in Case II, applying Theorem 2 to $\beta =Y_i$ and $u=X_i$ with $\mathrm{wt}(Y_i)=k$ and $\mathrm{wt}(X_i)=k+i^{\prime }$ for some $i^{\prime }\ge 1$, we then get

$$\begin{aligned} b_{i,i}=a_0^{(i^{\prime })}={0+i^{\prime }-1\atopwithdelims ()0}=1. \end{aligned}$$

This completes the proof. $\Box$

4.3 A new construction of Boolean functions on odd variables with optimal AI and high nonlinearity

In this subsection, we give a new construction of Boolean function $f$ with $\mathrm{supp}(f)=\left(W^{\ge k+1}\backslash U\right)\cup T$, where $T$ and $U$ are two properly chosen subsets of $W^{\le k}$ and $W^{\ge k+1}$ respectively. We will prove that the new constructed Boolean function $f$ has optimal AI and higher nonlinearity compared with the function defined in [8].

In this subsection, we always assume that $m=\lfloor {n\over 4}\rfloor$ with $n\ge 11$ being odd. That is, $n=4m+1$ with $m\ge 3$ or $n=4m+3$ with $m\ge 2$. Further, we always denote $t=\lceil {m+1\over 3}\rceil$ and $p=\lceil \log _2t\rceil$ in this subsection.

Set $\mathbb F _2^p=\left\{ e_1^{(p)},e_2^{(p)},\ldots ,e_{2^p}^{(p)}\right\}$, where the vectors are listed according to the Hamming weight firstly and the lexicographic order secondly. Denote $T_0=\bigcup \limits _{j=0}^3W^{k-j}$ and $U_0=\bigcup \limits _{j=0}^3W^{k+4-j}$. With these notations, we define $2m+2$ subsets $T_i$ and $U_i$ of $\mathbb F _2^n,\,1\le i\le m+1$, as follows:

• (1) $1\le i\le t$,

  $$\begin{aligned}&T_i =\{\beta =(y_1,0,y_2,0,y_3,e_{i}^{(p)},0)\in \mathbb F _2^{4i-4}\times \mathbb F _2^4\times \mathbb F _2^{4t-4i}\times \mathbb F _2\times \mathbb F _2^{n-4t-p-2}\times \mathbb F _2^{p}\\&~~~~~~~~\times \mathbb F _2|\beta \in T_0\}\\&U_i=\{u=(y_1,1,y_2,0,y_3,e_{i}^{(p)},0)\in \mathbb F _2^{4i-4}\times \mathbb F _2^4\times \mathbb F _2^{4t-4i}\times \mathbb F _2\times \mathbb F _2^{n-4t-p-2}\times \mathbb F _2^{p}\\&~~~~~~~~\times \mathbb F _2| u\in U_0\} \end{aligned}$$

• (2) $t+1\le i\le \min \{2t,m\}$,

  $$\begin{aligned} T_i=\{\beta =(0,e_{i-t}^{(p)},y_1,0,y_2,1)\in \mathbb F _2 \times \mathbb F _2^{p}\times \mathbb F _2^{4i-5-p}\times \mathbb F _2^4\times \mathbb F _2^{n-4i-1} \times \mathbb F _2| \beta \in T_0\}\\ U_i=\{u=(0,e_{i-t}^{(p)},y_1,1,y_2,1)\in \mathbb F _2\times \mathbb F _2^{p}\times \mathbb F _2^{4i-5-p}\times \mathbb F _2^4\times \mathbb F _2^{n-4i-1}\times \mathbb F _2| u\in U_0\} \end{aligned}$$

• (3) $\min \{2t,m\}+1\le i\le m$,

  $$\begin{aligned}&T_i=\{\beta =(1,e_{i-2t}^{(p)},y_1,1,y_2,0,y_3)\in \mathbb F _2 \times \mathbb F _2^{p}\times \mathbb F _2^{4t-1-p} \times \mathbb F _2\times \mathbb F _2^{4i-5-4t}\times \mathbb F _2^4\times \\&~~~~~~~~\mathbb F _2^{n-4i}|\beta \in T_0\}\\&U_i=\{u=(1,e_{i-2t}^{(p)},y_1,1,y_2,1,y_3)\in \mathbb F _2\times \mathbb F _2^{p}\times \mathbb F _2^{4t-1-p} \times \mathbb F _2\times \mathbb F _2^{4i-5-4t}\times \mathbb F _2^4\times \\&~~~~~~~~\mathbb F _2^{n-4i}| u\in U_0\} \end{aligned}$$

• (4) $i=m+1$,

  $$\begin{aligned}&T_{m+1}=\{\beta =(1,e_\lambda ^{(p)},y_1,1,y_2,0)\in \mathbb F _2\times \mathbb F _2^{p}\times \mathbb F _2^{4t-1-p} \times \mathbb F _2\times \mathbb F _2^{4m-4t-1}\times \\&~~~~~~~~~~~~~\mathbb F _2^{n-4m}| \beta \in T^{\prime }\}\\&U_{m+1}=\{u=(1,e_\lambda ^{(p)},y_1,1,y_2,1)\in \mathbb F _2\times \mathbb F _2^{p}\times \mathbb F _2^{4t-1-p}\times \mathbb F _2\times \mathbb F _2^{4m-4t-1}\times \\&~~~~~~~~~~~~~\mathbb F _2^{n-4m}| u\in U^{\prime }\} \end{aligned}$$

where $\lambda =m+1-\min \{2t,m\}$, and $T^{\prime }=W^k,\,U^{\prime }=W^{k+1}$ if $n=4m+1$, or $T^{\prime }=W^{k}\cup W^{k-2} ,\,U^{\prime }=W^{k+3}\cup W^{k+1}$ if $n=4m+3$.

Note that $|T_i|=|U_i|$ for $1\le i\le m+1$, and $T_i\cap T_j= U_i\cap U_j=\emptyset$ for any $i\ne j$ by the first, the $(4t+1)th$ and the last entries of the vectors in $T_i$ and $U_i$ and by the $e_i^{(p)}$’s.

Example 1

For $n=21$ and $23$, some specific elements in $T_i$ and $U_i$ are illustrated in Tables 1 and 2.

Table 1 Specific elements in $T_i$ and $U_i$ for $n=21$

Table 2 Specific elements in $T_i$ and $U_i$ for $n=23$

Based on the subsets $T_i$ and $U_i,\,1\le i\le m+1$, set

$$\begin{aligned} T=\bigcup _{i=1}^{m+1} T_i ~\mathrm{and} ~U=\bigcup _{i=1}^{m+1} U_i. \end{aligned}$$

(14)

Now, we are able to give a new construction of Boolean functions as follows, which have optimal AI and high nonlinearity.

With $T$ and $U$ being subsets of $\mathbb F _2^n$ given by (14), define $f\in \mathcal B _n$ as

$$\begin{aligned} f(x)=\left\{ \begin{array}{ll} F(x)+1,&x\in T\cup U\\ F(x),&\mathrm{otherwise} \end{array}\right. \end{aligned}$$

(15)

where $F(x)$ is the majority function on $n$ variables.

In what follows, the algebraic immunity and nonlinearity of $f$ in (15) are investigated respectively. Further, the ability of $f$ to resist fast algebraic attacks is also checked for $n=11,13$ and $15$.

For convenience, we respectively arrange all vectors in $T_i$ and $U_i,\,1\le i\le m+1$, according to the Hamming weight firstly and the lexicographic order secondly. Suppose

$$\begin{aligned} T_i=\{\beta _1^{(i)},\beta _2^{(i)},\ldots ,\beta _{|T_i|}^{(i)}\},~ U_i=\{u_1^{(i)},u_2^{(i)},\ldots ,u_{|T_i|}^{(i)}\} \end{aligned}$$

(16)

for $1\le i\le m+1$. By the definition of $T_i$ and $U_i$, obviously $\beta _j^{(i)}\preceq u_j^{(i)}$, for $1\le j\le |T_i|$ and $1\le i\le m+1$. More precisely, if $\mathrm{wt}(\beta _j^{(i)})=k-j^{\prime }$ with $0\le j^{\prime } \le 3$, then $\mathrm{wt}(u_j^{(i)})=k+4-j^{\prime }$, for $1\le j\le |T_i|$ and $1\le i \le m$. Hence, from Theorem 2, we know that the corresponding coefficient $b_{j,j}$ in (13) is

$$\begin{aligned} b_{j,j}=a_{j^{\prime }}^{(4-j^{\prime })}={3\atopwithdelims ()j^{\prime }}=1~(\mathrm{mod}~2). \end{aligned}$$

When $n=4m+1$, it follows from the definition of $T_{m+1}$ and $U_{m+1}$ that $\mathrm{wt}(\beta _{j}^{(m+1)})=k$ and $\mathrm{wt}(u_{j}^{(m+1)})=k+1,\,1\le j\le |T_{m+1}|$. By Theorem 2, we have $b_{j,j}=a_{0}^{(1)}=1$. When $n=4m+3$, similarly, $\mathrm{wt}(\beta _{j}^{(m+1)})=k$ (resp. $k-2$) and $\mathrm{wt}(u_{j}^{(m+1)})=k+3$ (resp. $k+1$), $1\le j\le |T_{m+1}|$. Then from Theorem 2 we know that $b_{j,j}=a_{0}^{(3)}=1$ or $b_{j,j}=a_{2}^{(1)}=1$. That is, the vectors in $T_i$ and $U_i,\,1\le i\le m+1$, satisfy Condition C1.

Next we check that the vectors in $T_i$ and $U_i,\,1\le i\le m+1$, satisfy Condition C2. Define

$$\begin{aligned} \varLambda _i=\{4i-3,4i-2,4i-1,4i\},1\le i\le m,~\mathrm{and~}\varLambda _{m+1}=\{4m+1,\ldots ,n\}. \end{aligned}$$

(17)

Note that the set $\varLambda _i,\,1\le i\le m+1$, contains the positions where $\beta _{j}^{(i)}\in T_i$ and $u_{j}^{(i)}\in U_i,\,1\le j\le |T_i|$, differ. We observe the following properties (e.g. Example 1) from the definition of the subsets $T_i$ and $U_i$ that

• $\beta _{j_2}^{(i)}\not \preceq \beta _{j_1}^{(i)},\,1\le j_1 <j_2\le |T_i|$ and $1\le i\le m+1$, follows from the order of the Hamming weight firstly and the lexicographic order secondly, which implies $\beta _{j_2}^{(i)}\not \preceq u_{j_1}^{(i)}$ since all the entries in $\beta _{j}^{(i)}$ and $u_{j}^{(i)},\,1\le j\le |T_i|$, are the same except for the ones at the fixed positions in $\varLambda _i$;

• Similarly $e_{i_2}^{(p)}\not \preceq e_{i_1}^{(p)},\,1\le i_1<i_2\le p$, which indicates $\beta _{j_2}^{(i_2)}\not \preceq u_{j_1}^{(i_1)}$ for $1\le j_1\le |T_{i_1}|,\,1 \le j_2\le |T_{i_2}|$, and $1\le i_1< i_2 \le t$ or $t+1\le i_1< i_2 \le \min \{2t,m\}$ or $\min \{2t,m\}+1\le i_1< i_2 \le m+1$;

• $\beta _{j_2}^{(i_2)}\not \preceq u_{j_1}^{(i_1)},\,1\le j_1\le |T_{i_1}|,\,1 \le j_2\le |T_{i_2}|$,

  • for $1\le i_1 \le t<i_2\le \min \{2t,m\}$ by the last entries of $\beta _{j_2}^{(i_2)}$ and $u_{j_1}^{(i_1)}$;

  • for $1\le i_1\le t$ and $\min \{2t,m\}+1\le i_2\le m+1$ by the $(4t+1)$th entries of $\beta _{j_2}^{(i_2)}$ and $u_{j_1}^{(i_1)}$;

  • for $t+1\le i_1\le \min \{2t,m\} <i_2\le m+1$ by the first entries of $\beta _{j_2}^{(i_2)}$ and $u_{j_1}^{(i_1)}$.

Thus, the following theorem holds.

Theorem 3

For $n\ge 11$, the function $f\in \mathcal B _n$ constructed in (15) has optimal AI.

Now, we study the nonlinearity of the Boolean function $f$ constructed in (15). First of all, we need some useful lemmas.

Lemma 1

For $1\le i\le 2^p$, denote $\mathrm{wt}(e_{i}^{(p)})$ by $s_i$. Then,

$$\begin{aligned} |T_i|=|U_i|=\left\{ \begin{array}{ll} {2k-4-p\atopwithdelims ()k-s_i}+{2k-4-p\atopwithdelims ()k-2-s_i},&1\le i\le t, \\ {2k-4-p\atopwithdelims ()k-1-s_{i-t}}+{2k-4-p\atopwithdelims ()k-3-s_{i-t}},&t+1\le i\le \min \{2t,m\}, \\ {2k-4-p\atopwithdelims ()k-2-s_{i-2t}}+{2k-4-p\atopwithdelims ()k-4-s_{i-2t}},&\min \{2t,m\}+1\le i\le m, \\ {2k-4-p\atopwithdelims ()k-2-s_{\lambda }}+ {2k-4-p\atopwithdelims ()k-4-s_{\lambda }},&i=m+1, n=4m+3,\\ {2k-2-p\atopwithdelims ()k-2-s_{\lambda }},&i=m+1, n=4m+1, \end{array}\right. \end{aligned}$$

(18)

where $\lambda =m+1-\min \{2t,m\}$.

Proof

By the definition of $T_i$ and $U_i$, it is easy to see that

$$\begin{aligned}|T_i|=|U_i|= \left\{ \begin{array}{ll} \sum \limits _{j=0}^{3}{2k-5-p\atopwithdelims ()k-j-s_i},&1\le i\le t, \\ \sum \limits _{j=0}^{3}{2k-5-p\atopwithdelims ()k-j-1-s_{i-t}},&t+1\le i\le \min \{2t,m\},\\ \sum \limits _{j=0}^{3}{2k-5-p\atopwithdelims ()k-j-2-s_{i-2t}},&\min \{2t,m\}+1\le i\le m, \\ {2k-4-p\atopwithdelims ()k-2-s_{\lambda }}+{2k-4-p\atopwithdelims ()k-4-s_{\lambda }},&i=m+1, n=4m+3,\\ {2k-2-p\atopwithdelims ()k-2-s_{\lambda }},&i=m+1, n=4m+1. \end{array}\right. \end{aligned}$$

Immediately, (18) follows from Pascal’s Formula. $\Box$

Lemma 2

The cardinality of $T_i,\,1\le i\le m+1$, in (18) satisfies

$$\begin{aligned} \min \limits _{1\le i\le m+1}|T_i|=|T_1|= {2k-4-p\atopwithdelims ()k}+{2k-4-p\atopwithdelims ()k-2}. \end{aligned}$$

(19)

Proof

Clearly, for $1\le i\le 2^p$, we have $0\le s_i=\mathrm{wt}(e_{i}^{(p)})\le p$ with $s_1=0$ since $e_1^{(p)}=(0,0,\ldots ,0)$. Subsisting it into (18), we can easily get

$$\begin{aligned} \min \limits _{1\le i\le m}|T_i|=|T_1|= {2k-4-p\atopwithdelims ()k}+{2k-4-p\atopwithdelims ()k-2} \end{aligned}$$

by means of the facts that ${a\atopwithdelims ()b}<{a\atopwithdelims ()c}$ if $|b-a/2|>|c-a/2|$.

As for $|T_{m+1}|$, if $n=4m+3$, then $|T_{m+1}|\ge {2k-4-p\atopwithdelims ()k}+{2k-4-p\atopwithdelims ()k-2}$; if $n=4m+1$, then $|T_{m+1}|={2k-2-p\atopwithdelims ()k-2-s_{m+1-\min \{2t,m\}}} \ge {2k-2-p\atopwithdelims ()k-2-p}$. Further, applying Pascal’s Formula, we have ${2k-2-p\atopwithdelims ()k-2-p}={2k-2-p\atopwithdelims ()k}={2k-3-p\atopwithdelims ()k}+{2k-3-p\atopwithdelims ()k-1}={2k-4-p\atopwithdelims ()k}+{2k-4-p\atopwithdelims ()k-1}+{2k-4-p\atopwithdelims ()k-1}+{2k-4-p\atopwithdelims ()k-2}>{2k-4-p\atopwithdelims ()k}+{2k-4-p\atopwithdelims ()k-2}$, which gives the desired (19). $\Box$

Lemma 3

([14, 27]) Let $F(x)$ be the $n$-variable majority function with $n$ odd. Then the Walsh spectrum of $F(x)$ satisfies

• 1. $W_F(\omega )=2{2k\atopwithdelims ()k}$ if $\mathrm{wt}(\omega )=1$;

• 2. $W_F(\omega )=2(-1)^{k}{2k\atopwithdelims ()k}$ if $\mathrm{wt}(\omega )=n$;

• 3. $|W_F(\omega )|\le 2\big [{2k-2\atopwithdelims (){k-1}}-{2k-2\atopwithdelims ()k}\big ]$ if $2\le \mathrm{wt}(\omega )\le 2k$ and $n\ge 7$.

Now, we are ready to compute the nonlinearity of the function $f$ given in (15).

Theorem 4

For $n\ge 11$ being odd, the nonlinearity of $f\in \mathcal B _n$ constructed in (15) is

$$\begin{aligned} nl_f= 2^{2k}-{2k\atopwithdelims ()k}+2\Bigg [{2k-4-p\atopwithdelims ()k}+{2k-4-p\atopwithdelims ()k-2}\Bigg ] \end{aligned}$$

where $p=\lceil \log _2 \lceil {m+1\over 3}\rceil \rceil ,\,m=\lfloor {n\over 4}\rfloor$ and $k=\frac{n-1}{2}$.

Proof

Firstly, it is clear that $W_f(0)=0$ since $f$ is balanced.

Next, if $\omega =(\omega _1,\omega _2,\ldots ,\omega _n)\ne 0$, by (3), we have

$$\begin{aligned} W_f(\omega )&= \sum \limits _{x\not \in T\cup U }(-1)^{f(x)\oplus \omega \cdot x}+ \sum \limits _{x\in T}(-1)^{1\oplus \omega \cdot x}+ \sum \limits _{x\in U}(-1)^{\omega \cdot x}\nonumber \\&= W_F(\omega )-2\bigg [\sum \limits _{x\in T}(-1)^{\omega \cdot x}-\sum \limits _{x\in U}(-1)^{\omega \cdot x}\bigg ]\nonumber \\&= W_F(\omega )-2\sum \limits _{i=1}^{m+1}\bigg [\sum \limits _{x\in T_i}(-1)^{\omega \cdot x}-\sum \limits _{x\in U_i}(-1)^{\omega \cdot x}\bigg ] \end{aligned}$$

(20)

Note that the corresponding vectors $\beta _j^{(i)}\in T_i$ and $u_j^{(i)}\in U_i$ in (16) are almost the same except for the entries at the positions in $\varLambda _i$ defined in (17). Hence,

$$\begin{aligned} \sum \limits _{x\in T_i}(-1)^{\omega \cdot x}-\sum \limits _{x\in U_i}(-1)^{\omega \cdot x}= \big [1-(-1)^{\sum _{l\in \varLambda _i}\omega _{l}}\big ]\sum \limits _{x\in T_i}(-1)^{\omega \cdot x} \end{aligned}$$

which will be discussed in the following three cases.

• Case 1. If $\mathrm{wt}(\omega )=1$, assuming $\mathrm supp (\omega )=\{j\}$ for some $1\le j\le n$, then $\sum _{x\in T_i}(-1)^{\omega \cdot x}-\sum _{x\in U_i}(-1)^{\omega \cdot x}=0$ if $i\ne \lceil {j\over 4}\rceil$ due to $\omega _{l}=0$ for all $l\in \varLambda _i$. Otherwise, if $i=\lceil {j\over 4}\rceil$, then

  $$\begin{aligned} \sum \limits _{x\in T_{i}}(-1)^{\omega \cdot x}-\sum \limits _{x\in U_{i}}(-1)^{\omega \cdot x} =2|T_{i}| \end{aligned}$$

  because of $\omega \cdot x=0$ for all $x\in T_i$. Thus, applying (19) and Lemma 3 to (20), it results in

  $$\begin{aligned} |W_f(\omega )|&\le \big |W_F(\omega )-4\min \limits _{1\le i\le m+1}|T_i|\big |\\&= 2{2k\atopwithdelims ()k}-4\Bigg [{2k-4-p\atopwithdelims ()k}+{2k-4-p\atopwithdelims ()k-2}\Bigg ] \end{aligned}$$

  since $2{2k\atopwithdelims ()k}=4{2k-1\atopwithdelims ()k}>4|T_i|$ holds for all $1\le i\le m+1$.

• Case 2. If $\mathrm{wt}(\omega )=n$, i.e., $\omega =(1,1,\ldots ,1)$, then $\sum _{x\in T_i}(-1)^{\omega \cdot x}-\sum _{x\in U_i}(-1)^{\omega \cdot x}=0$ for $1\le i\le m$, since $\sum _{l\in \varLambda _i}\omega _{l}=4$. While,

  $$\begin{aligned} \sum \limits _{x\in T_{m+1}}(-1)^{\omega \cdot x}-\sum \limits _{x\in U_{m+1}}(-1)^{\omega \cdot x} =2(-1)^k|T_{m+1}| \end{aligned}$$

  because of $\sum _{l\in \varLambda _{m+1}}\omega _{l}=1$ and $T_{m+1}\subseteq W^k$ if $n=4m+1$, or $\sum _{l\in \varLambda _{m+1}}\omega _{l}=3$ and $T_{m+1}\subseteq W^{k}\cup W^{k-2}$ if $n=4m+3$. Associated with Lemma 3 and (19), it leads to

  $$\begin{aligned} |W_f(\omega )|&= \Bigg |2(-1)^{k}{2k\atopwithdelims ()k}-4(-1)^{k}|T_{m+1}|\Bigg |\\&\le 2{2k\atopwithdelims ()k}-4\Bigg [{2k-4-p\atopwithdelims ()k}+{2k-4-p\atopwithdelims ()k-2}\Bigg ] \end{aligned}$$

• Case 3. If $2\le \mathrm{wt}(\omega )\le 2k$, then by Lemma 3 we have

  $$\begin{aligned} |W_f(\omega )|&\le 2{2k-2\atopwithdelims ()k-1}-2{2k-2\atopwithdelims ()k}+ 4\sum _{i=1}^{m+1}|T_i|\\&= {1\over 2k-1}{2k\atopwithdelims ()k}+4|T| \end{aligned}$$

  Denote

  $$\begin{aligned} \varDelta =2{2k\atopwithdelims ()k}-4\min \limits _{1\le i\le m+1}|T_i|-{1\over 2k-1}{2k\atopwithdelims ()k}-4|T|. \end{aligned}$$

  Next we will prove that $\varDelta >0$ for $n\ge 11$. If $m\le 13$, we know that

  $$\begin{aligned} \varDelta&= 2{2k\atopwithdelims ()k}-4|T_1|-{1\over 2k-1}{2k\atopwithdelims ()k}-4|T|\\&= {4k-3\over 2k-1}{2k\atopwithdelims ()k}-8|T_1|-4\sum \limits _{i=2}^{ m+1}|T_i|\\&> 0 \end{aligned}$$

  by a direct calculation listed in the following Tables 3 and 4.

  Table 3 The value of $\varDelta$ for $n=4m+1$

  Table 4 The value of $\varDelta$ for $n=4m+3$

  If $m\ge 14$, we investigate it in two subcases according to $p$ is even or odd. When $p$ is even, by (18) we have

  $$\begin{aligned} |T_i|\le 2{2k-4-p\atopwithdelims ()k-2-{p\over 2}}, ~ 1\le i\le m \end{aligned}$$

  and

  $$\begin{aligned} |T_{m+1}|\le {2k-2-p\atopwithdelims ()k-1-{p\over 2}}\le 4{2k-4-p\atopwithdelims ()k-2-{p\over 2}}. \end{aligned}$$

  Then,

  $$\begin{aligned} \varDelta&= {4k-3\over 2k-1}{2k\atopwithdelims ()k}-4|T_1|-4\sum \limits _{i=1}^m|T_i|-4|T_{m+1}|\\&\ge {4k-3\over 2k-1}{2k\atopwithdelims ()k}-8(m+3){2k-4-p\atopwithdelims ()k-2-{p\over 2}}\\&\ge {4k-3\over 2k-1}{2k\atopwithdelims ()k}-{8(m+3)k\over 2^{3+\log _2{m+1\over 3}}(2k-3-p)}{2k\atopwithdelims ()k}\\&\ge \Big [{8m-3\over 4m-1}-{3(m+3)(2m+1)\over (m+1)(3m+8)}\Big ]{2k\atopwithdelims ()k}\\&= {m^2+16m-15\over (4m-1)(m+1)(3m+8)}{2k\atopwithdelims ()k}\\&> 0 \end{aligned}$$

  where in the second inequality we use

  $$\begin{aligned} {{2r\atopwithdelims ()r}\over {2k\atopwithdelims ()k} }={(2r)!(k!)^2\over (2k)!(r!)^2}={ k^2(k-1)^2\cdots (r+1)^2\over (2k)(2k-1)(2k-2)\cdots (2r+1)}<({1\over 2})^{2k-2r-1}{k\over 2r+1 } \end{aligned}$$

  (21)

  for $r=k-2-{p\over 2}$, and $p\ge \log _2{m+1\over 3}$; in the third inequality we use

  $$\begin{aligned} {4k-3\over 2k-1}\ge {8m-3\over 4m-1} \end{aligned}$$

  and

  $$\begin{aligned} {k\over 2k-3-p}\le {2m+1\over 4m-3-p}\le {2m+1\over 3m+8} \end{aligned}$$

  since $m-p\ge 11$ for $m\ge 14$, and $k=\lceil n/2\rceil -1$ is $2m$ if $n=4m+1$ or $2m+1$ if $n=4m+3$. When $p$ is odd, by (18) we then get

  $$\begin{aligned} |T_i|\le {2k-4-p\atopwithdelims ()k-2-{p+1\over 2}}+{2k-4-p\atopwithdelims ()k-2-{p-1\over 2}}={2k-3-p\atopwithdelims ()k-2-{p-1\over 2}} \end{aligned}$$

  for $1\le i\le m$, and

  $$\begin{aligned} |T_{m+1}|\le {2k-2-p\atopwithdelims ()k-1-{p-1\over 2}}<2{2k-3-p\atopwithdelims ()k-2-{p-1\over 2}}. \end{aligned}$$

  Similarly, we can derive that

  $$\begin{aligned} \varDelta =2{2k\atopwithdelims ()k}-4\min \limits _{1\le i\le m+1}|T_i|-{1\over 2k-1}{2k\atopwithdelims ()k}-4|T| >0. \end{aligned}$$

Therefore, for all $\omega \in \mathbb F _2^n$, we always have

$$\begin{aligned} |W_f(\omega )|\le 2{2k\atopwithdelims ()k}-4\Bigg [{2k-4-p\atopwithdelims ()k}+{2k-4-p\atopwithdelims ()k-2}\Bigg ] . \end{aligned}$$

Note that this bound is tight, since the bound can be attained in case 1 with equality $\min _{1\le i\le m+1}|T_i|=|T_1|$.

We complete the proof for $n\ge 11$ by applying (4) to the above inequality. $\Box$

Recall that in our construction $p$ is defined as $p=\lceil \log _2 \lceil {m+1\over 3}\rceil \rceil$. If $p=\log _2 {m+1\over 3}$, then each vector $e_i^{(p)},\,1\le i \le 2^p$, is used three times for constructing $T_1,T_2,\ldots ,T_{m+1}$. However, if $n=4m+1$ with $3\cdot 2^p-1\ge m+1$, i.e., $m=3,4,6,7,8,9,10,12,13,\ldots$, then some subsets of $e_2^{(p)},\ldots ,e_{2^p}^{(p)},e_1^{(p)},\ldots , e_{2^p}^{(p)},\,e_1^{(p)},\ldots ,e_{2^p}^{(p)}$ are enough to construct $T_1,T_2,\ldots ,T_{m+1}$; if $n=4m+3$ with $3\cdot 2^p-2\ge m+1$, i.e., $m=3,6,7,8,9,12,13,\ldots$, then some subsets of $e_2^{(p)},\ldots ,e_{2^p}^{(p)},e_1^{(p)},\ldots ,e_{2^p}^{(p)},\,e_1^{(p)},\ldots ,e_{2^p-1}^{(p)}$ are enough to construct $T_1,T_2,\ldots ,T_{m+1}$. In this way, by the same method as we did in Lemmas 1 and 2, we have

$$\begin{aligned} \min \limits _{1\le i\le m+1}|T_i|=|T_1|= {2k-4-p\atopwithdelims ()k-1}+{2k-4-p\atopwithdelims ()k-3}. \end{aligned}$$

Then, by the same method as we did in Theorem 4, the nonlinearity of $f\in \mathcal B _n$ constructed in (15) can be improved as

$$\begin{aligned} nl_f^{\prime }= 2^{2k}-{2k\atopwithdelims ()k}+2\Bigg [{2k-4-p\atopwithdelims ()k-1}+{2k-4-p\atopwithdelims ()k-3}\Bigg ]. \end{aligned}$$

To the best of our knowledge, among all the Boolean functions constructed from the generator matrix of Reed–Muller code, the ones proposed in [8] have the highest nonlinearity. When $n$ is odd, the functions in [8] have nonlinearity

$$\begin{aligned} nl_g=2^{n-1}-{2k\atopwithdelims ()k}+2\left\lfloor \sum \limits _{i=0}^{m-1}{3m-2\atopwithdelims ()m+i-1 }{m-i\over m}\right\rfloor \end{aligned}$$

for $n=4m+1,m\ge 4$, and

$$\begin{aligned} nl_g=2^{n-1}-{2k \atopwithdelims ()k}+2\left\lfloor \sum \limits _{i=0}^{m+1}{3m-1\atopwithdelims ()m+i}{m+2-i\over m+2}\right\rfloor \end{aligned}$$

for $n=4m+3,m\ge 5$.

Let us consider the enhanced nonlinearity of our functions and the ones in [8] over that of the majority function. For simplicity, denote

$$\begin{aligned}&\varDelta _1 = \left\{ \begin{array}{ll} 2\left\lfloor \sum \limits _{i=0}^{m-1}{3m-2\atopwithdelims ()m+i-1 }{m-i\over m}\right\rfloor , n=4m+1,m\ge 4 \\ 2\left\lfloor \sum \limits _{i=0}^{m+1}{3m-1\atopwithdelims ()m+i}{m+2-i\over m+2}\right\rfloor , n=4m+3,m\ge 5 \end{array} \right.\\&\varDelta _2 = 2\Bigg [{2k-4-p\atopwithdelims ()k}+{2k-4-p\atopwithdelims ()k-2}\Bigg ] \\&\varDelta _3 = 2\Bigg [{2k-4-p\atopwithdelims ()k-1}+{2k-4-p\atopwithdelims ()k-3}\Bigg ] \end{aligned}$$

where we assume $\varDelta _3$ be equal to $\varDelta _2$ for $n=4m+1$ with $3\cdot 2^p-1\ge m+1$ or $n=4m+3$ with $3\cdot 2^p-2\ge m+1$

By a direct calculation, we know that

$$\begin{aligned} \varDelta _1 =\sum \limits _{i=0}^m{{3m-2}\atopwithdelims (){m+i-1}} <(m+1){{3m-2}\atopwithdelims (){\lfloor {3m\over 2}\rfloor }-1}\le 3\cdot 2^p{{3m-2}\atopwithdelims (){\lfloor {3m\over 2}\rfloor }-1} \end{aligned}$$

for $n=4m+1$, and

$$\begin{aligned} \varDelta _1 <2(m+1){3m-1\atopwithdelims ()\lfloor {3m-1\over 2}\rfloor }\le 6\cdot 2^p{3m-1\atopwithdelims ()\lfloor {3m-1\over 2}\rfloor } \end{aligned}$$

for $n=4m+3$. On the other hand,

$$\begin{aligned} \varDelta _2> 2{2k-4-p\atopwithdelims ()k-2}=2{2k-4-p\atopwithdelims ()k-2-p}>2{2k-4-2p\atopwithdelims ()k-2-p}. \end{aligned}$$

If $n=4m+1$, then

$$\begin{aligned} { \varDelta _2\over \varDelta _1}>{2{4m-4-2p\atopwithdelims ()2m-2-p}\over 3\cdot 2^p{{3m-2}\atopwithdelims (){\lfloor {3m\over 2}\rfloor }-1}}>{2\over 3\cdot 2^p}2^{m-3-2p}{3m-1\over 2m-2-p}>2^{m-3-3p} \end{aligned}$$

where the second inequality holds by the same method as we did in (21). If $n=4m+3$, similarly

$$\begin{aligned} { \varDelta _2\over \varDelta _1}>{2{4m-2-2p\atopwithdelims ()2m-1-p}\over 6\cdot 2^p{3m-1\atopwithdelims ()\lfloor {3m-1\over 2}\rfloor }}>{2\over 6\cdot 2^p}2^{m-2-2p}{3m\over 2m-1-p}>2^{m-3-3p}. \end{aligned}$$

When $m\le 11$, some concrete values of the enhanced nonlinearities $\varDelta _1,\,\varDelta _2$, and $\varDelta _3$ are given in Tables 5 and 6.

Table 5 Comparison of the enhanced nonlinearity for $n=4m+1$

Table 6 Comparison of the enhanced nonlinearity for $n=4m+3$

In 2008, Carlet and Feng [5] proposed an infinite class of balanced functions(Carlet–Feng functions) with optimal algebraic immunity, the nonlinearity of which satisfies

$$\begin{aligned} nl_g\ge 2^{n-1}+\frac{2^{\frac{n}{2}+1}}{\pi }\ln \Big (\frac{\pi }{4(2^n-1)}\Big )-1. \end{aligned}$$

In 2011, Zeng et al. [29] improved the lower bound of the nonlinearity of Carlet–Feng function to be

$$\begin{aligned} nl_g> 2^{n-1}-\Big (\frac{\ln 2}{3}(n-1)+\frac{5}{6}+\frac{1}{3\sqrt{3}}+\frac{1}{6\sqrt{2}}\Big )2^{\frac{n}{2}}-1. \end{aligned}$$

In 2012, Tang et al. [28] presented a much better lower bound of the nonlinearity of Carlet–Feng function as

$$\begin{aligned} nl_{g}>2^{n-1}-\Big (\frac{n\ln 2}{\pi }+0.74\Big )2^{\frac{n}{2}}-1. \end{aligned}$$

For $11\le n\le 21$ with $n$ odd, the comparison of nonlinearity of our function with nonlinearity of the majority function, the above three lower bounds on nonlinearity of the Carlet–Feng function, and the upper bound $\lceil 2^{n-1} - 2^{n-1\over 2}\rceil$ is given in Table 7.

Table 7 Comparison of the nonlinearity for $11\le n\le 21$ with $n$ odd

It should be noted that the actual value of the nonlinearity of Carlet–Feng function is significantly larger than the lower bounds above. Then, the nonlinearity of our function is not as good as that of Carlet–Feng function. Nevertheless, the most useful properties of Boolean function based on the generator matrix of Reed–Muller code are the efficient computation and easy implementation. In order to construct Boolean function with optimal algebraic immunity and higher nonlinearity in this way, according to the computation of Walsh spectrum, we should construct two larger sets $T\subseteq W^{\le k}$ and $U\subseteq W^{\ge k+1}$ such that the nonsingular matrix $B$ in (13) is a more generalized one instead of an upper triangular matrix or a lower triangular matrix.

At last, we analyze the resistance to fast algebraic attacks of the function $f\in \mathcal B _n$ constructed in (15) for $n=11,13,15$. It is known that an $n$-variable Boolean function $f$ can be considered as optimal with respect to fast algebraic attacks if there do not exist two nonzero functions $g$ and $h$ such that $fg=h$ and $\mathrm{deg}(g)+\mathrm{deg}(h)<n$ with $\mathrm{deg}(g)<\frac{n}{2}$. Nevertheless, the resistance to fast algebraic attacks turns out to be hard to estimate, and we must rely on computer simulations feasible only for relatively small value of $n$. Denote

$$\begin{aligned} \varOmega _f=\min \{\mathrm{deg}(g)+\mathrm{deg}(h)|0\ne g,h\in \mathcal B _n, fg=h\} \end{aligned}$$

We have checked the resistance of our functions to the fast algebraic attacks for $n=11,13$ and $15$. The results are that if $n=11$ then $\varOmega _f=8$; if $n=13$ then $\varOmega _f=10$; if $n=15$ then $\varOmega _f=12$. We conjecture that $\varOmega _f=n-3$. If this conjecture is true, we can say that the behavior of our functions against fast algebraic attacks is not too bad although these functions are not optimal with respect to fast algebraic attacks.

5 Conclusion

In this paper, an important property about the $k$th order Reed–Muller code $\text{ RM}(k,n)$ is proved by studying the linear relationship of the column vectors in its generator matrix $G$. This property can be used to provide simple and efficient proofs for AI properties of the Boolean functions in some known constructions. The study also leads to a new class of Boolean functions with optimal AI and high nonlinearity. Although it is still a small subset of all such functions with optimal AI, in terms of practical applications our constructions provide a large source of such functions. In addition, there are still some problems needing to be studied further such as how to improve the nonlinearity and how to give a rigorous proof of our conjecture on the behavior against fast algebraic immunity.