A New Construction of Weightwise Perfectly Balanced Functions with High Weightwise Nonlinearity

Abstract

The FLIP cipher was proposed at Eurocrypt 2016 for the purpose of meliorating the efficiency of fully homomorphic cryptosystems. Weightwise perfectly balanced Boolean functions meet the balancedness requirement of the filter function in FLIP ciphers, and the construction of them has attracted serious attention from researchers. Nevertheless, the literature is still thin. Modifying the supports of functions with a low degree is a general construction technique whose key problem is to find a class of available low-degree functions. We first seek out a class of quadratic functions and then, based on these functions, present the new construction of weightwise perfectly balanced Boolean functions by adopting an iterative approach. It is worth mentioning that the functions we construct have good performance in weightwise nonlinearity. In particular, some p-weight nonlinearities achieve the highest values in the literature for a small number of variables.

1. Introduction

With the development of cloud services, the privacy protection of data stored in the cloud has become particularly important. One solution to providing secure cloud computing on untrusted public clouds is Fully Homomorphic Encryption. This encryption scheme supports the computation of encrypted data in a homomorphic way without needing decryption on the cloud. Cloud services based on FHE frameworks play a role in many applications, such as private data banks, encrypted search and multi-party security calculations, while they have the well-known bottlenecks: high computational cost and limited homomorphic capacity. See [1,2] for details.

To mitigate the bottlenecks and improve the efficiency of homomorphic encryption for an acceptable fully homomorphic cryptosystem, Méaux et al. [2] presented a new type of stream cipher, denoted as a filter permutator, at Eurocrypt 2016. They gave a general structure of filter permutators as shown in Figure 1 [2]. A filter permutator consists of three parts: the key register, which stores the original key; the permutation generator, which is parameterized by a Pseudo Random Number Generator (PRNG) and generates a permutation P to permute the key from the register; and the filter function, which filters the permuted key to output the key stream.

Lastly, the encryption (resp. decryption) needs to XOR the key stream with the plaintext (resp. ciphertext) to generate the ciphertext (resp. plaintext). A family of filter permutators, called FLIP, is specified. FLIP utilizes Knuth shuffle as the permutation generator parameterized by a forward secure PRNG based on the AES-128 and takes the direct sum of three Boolean functions as the filter function.

Different from the Boolean function used in traditional stream ciphers, the inputs of the Boolean function acting as a filter function in FLIP come from different permutations of the same key and, therefore, have the same Hamming weight. As a result, in order to construct the filter function in FLIP, Boolean functions with restricted input, studied early in [3,4], have now become a class of functions of great interest in cryptography.

It has been shown that, for Boolean functions with restricted input, balancedness, nonlinearity and algebraic immunity continue to play a vital role in the corresponding attacks on somewhat homomorphic cryptosystems in the framework of FLIP ciphers (see [5,6]). Considering the first general cryptographic requirement, these functions need to be balanced. Therefore, weightwise perfectly balanced (WPB) Boolean functions become the focus of research on Boolean functions with restricted input.

If a Boolean function is always balanced when restricted to each subset of ${\mathbb{F}}_2^n$ with the same Hamming weight (not equal to 0 or n) and has different outputs when the input’s Hamming weight is 0 and n, it is called a WPB function. In 2017, Carlet et al. constructed the first class of WPB functions using recursive methods for FLIP [6]. In 2019, the author in reference [7] proposed a class of WPB functions that belong to two-rotation symmetric Boolean functions. Some classes of WPB functions are presented by modifying the supports of Boolean functions with low algebraic degree not larger than 4 in [8,9,10].

The reference [11] analyzed the lower bound of weightwise nonlinearity of one class of WPB functions. A family of WPB functions with the maximal algebraic immunity is given in [12], and based on them, Mesnager et al. proposed two new concrete ones in 2022 [13]. Although WPB functions have attracted great attention, it is still challenging work to construct this class of functions, particularly the ones with other good cryptographic properties.

As mentioned above, modifying the supports of Boolean functions with low algebraic degree is a useful technique, which has been used in [8,9,10] to build WPB functions. The focus of this technique is to find low-degree functions. The authors in [8,9,10] found different functions possessing degrees not higher than 4. In this paper, we obtain a class of quadratic Boolean functions whose p-weight is easy to analyze and calculate. Utilizing these functions, we propose a fresh class of $2^m$-variable WPB functions. We make a computer program and compute the p-weight nonlinearity of functions with a small number of variables. The experimental results show that our functions have significantly higher p-weight nonlinearity compared with the other main existing functions. In addition, we also analyze their algebraic degree and algebraic immunity.

The remainder of the paper is organized as follows. The formal definition and necessary preparations are introduced in Section 2. A class of quadratic Boolean functions is presented in Section 3. In Section 4, we give the construction of WPB functions and show the specific process of proving them. Then, we compare the p-weight nonlinearity of WPB functions with other papers. Finally, we conclude the paper with Section 5.

2. Preliminaries

Let ${\mathbb{F}}_2^n$ be the n-dimensional vector space over ${\mathbb{F}}_2$, $x=(x_1,x_2,\dots ,x_n)$ be a vector in ${\mathbb{F}}_2^n$, all zero vector $0_n=(0,0,\dots ,0)\in {\mathbb{F}}_2^n$, and all one vector $1_n=(1,1,\dots ,1)\in {\mathbb{F}}_2^n$. The mapping f from ${\mathbb{F}}_2^n$ to ${\mathbb{F}}_2$ is called an n-variable Boolean function. ${\mathcal{B}}_n$ is the set of all n-variable Boolean functions. Usually, f can be represented by its truth table, i.e.,

$$f=\left[f\right(0,0,\dots ,0),f(0,0,\dots ,1),\dots ,f(1,1,\dots ,1\left)\right].$$

For a vector $x\in {\mathbb{F}}_2^n$, we claim its support $\mathrm{supp}\left(x\right)$ is $\left\{1\le k\le n|x_k=1\right\}$, and its Hamming weight $\mathrm{wt}\left(x\right)$ is $\left|\mathrm{supp}\left(x\right)\right|$. With being regarded as a vector, the Hamming weight of f is $\mathrm{wt}\left(f\right)=\left|\mathrm{supp}\left(f\right)\right|$, where f’s support $\mathrm{supp}\left(f\right)$ is often described as the set of input vectors making f outputs 1—that is to say, $\mathrm{supp}\left(f\right)=\{x\in {\mathbb{F}}_2^n|f\left(x\right)=1\}$. If $\mathrm{wt}\left(f\right)$ takes the value $2^{n-1}$, we say that f is balanced.

In addition, f can be expressed by its algebraic normal form, i.e.,

$$f\left(x\right)=\underset{v\in {\mathbb{F}}_2^n}{⨁}{a}_v{x}^v,$$

where the coefficient $a_v\in {\mathbb{F}}_2$, $x^v=x_1^{v_1}{x}_2^{v_2}\dots x_n^{v_n}$. The algebraic degree of f is defined as

$$\mathrm{deg}\left(f\right)=max\left\{\mathrm{wt}\left(v\right)\right|v\in {\mathbb{F}}_2^n,a_v=1\}.$$

A Boolean function f is said to be affine if $\mathrm{deg}\left(f\right)\le 1$.

When talking about a Boolean function f with restricted input, we define it is p-weight support as

$${\mathrm{supp}}_p\left(f\right)=\{x\in {\mathbb{F}}_2^n|f\left(x\right)=1,\mathrm{wt}\left(x\right)=p\},$$

where $0\le p\le n$. The p-weight of f is

$${\mathrm{wt}}_p\left(x\right)=\left|{\mathrm{supp}}_p\left(f\right)\right|=\left|\left\{x\in \mathrm{supp}\left(f\right)\mid \mathrm{wt}\left(x\right)=p\right\}\right|.$$

(1)

For the sake of argument, we denote ${\mathrm{zeros}}_p\left(f\right)=\{x\in {\mathbb{F}}_2^n|f\left(x\right)=0,\mathrm{wt}\left(x\right)=p\}.$

Definition 1. 

Let $f\in {\mathcal{B}}_n$. We claim that f is a WPB Boolean function if ${\mathrm{wt}}_p\left(f\right)=\frac{1}{2}\left(\begin{array}{c}n\\ p\end{array}\right)$ for $1\le p\le n-1$ and $f\left(0_n\right)\ne f\left(1_n\right)$.

Thus far, the existing research has indicated that the number of variables of the WPB Boolean function is a power of 2 [6]. Therefore, the Boolean functions that we construct in this paper have $2^m$ variables.

In addition to the consideration of balancedness, the construction of Boolean functions should also consider meeting high nonlinearity to achieve resistance against fast correlation attacks. Nonlinearity is a particularly important cryptographic criterion of Boolean functions, which describes the minimum Hamming distance between a Boolean function and all affine functions. When the input of a Boolean function is restricted to the vector set $\{x\in {\mathbb{F}}_2^n\mid \mathrm{wt}\left(x\right)=p\}$ with integer $p\le n$, we call its nonlinearity p-weight nonlinearity.

Definition 2. 

Let $f\in {\mathcal{B}}_n$. For $0\le p\le n$, the p-weight nonlinearity of f is expressed as

$${\mathrm{NL}}_p\left(f\right)=\frac{1}{2}\left(\begin{array}{c}n\\ p\end{array}\right)-\frac{1}{2}\underset{a\in {\mathbb{F}}_2^n}{max}\left|\sum _{x\in {\mathbb{F}}_2^n,\mathrm{wt}\left(x\right)=p}{(-1)}^{f\left(x\right)\oplus a·x}\right|,$$

where $a·x=a_1{x}_1\oplus \cdots \oplus a_n{x}_n$. $\{{\mathrm{NL}}_1\left(f\right),{\mathrm{NL}}_2\left(f\right),\dots ,{\mathrm{NL}}_{n-1}\left(f\right)\}$ is called the weightwise nonlinearity of f.

Remarkably, reference [6] gives the upper bound of the p-weight nonlinearity of f as follows

$${\mathrm{NL}}_p\left(f\right)\le ⌊\frac{1}{2}\left(\begin{array}{c}n\\ p\end{array}\right)-\frac{1}{2}\sqrt{\left(\begin{array}{c}n\\ p\end{array}\right)}⌋,$$

where $\lfloor a\rfloor$ is the largest integer not greater than a.

Another well-known cryptographic criterion of Boolean functions is algebraic immunity, which should be as high as possible to make the Boolean function resist algebraic attacks.

Definition 3. 

Suppose $f\in {\mathcal{B}}_n$. The algebraic immunity of f is defined as

$$\mathrm{AI}\left(f\right)=min\left\{\mathrm{deg}\right(g)\mid g\in \mathrm{Ann}(f) \mathrm{or} \mathrm{Ann}(1\oplus f\left)\right\},$$

where $\mathrm{Ann}\left(f\right)=\{g\mid 0\ne g\in {\mathcal{B}}_n,fg=0\}$.

Previous studies have shown that $\mathrm{AI}\left(f\right)\le \lceil \frac{n}{2}\rceil$. Specially, if $\mathrm{AI}\left(f\right)$ reaches the value $\lceil \frac{n}{2}\rceil$, we say that f has the maximal algebraic immunity.

Next, we show the following two lemmas, which will be used later in the the paper.

Lemma 1. 

(Pascal’s Rule). Let k and j be two integers. We have

$$\left(\begin{array}{c}k\\ j\end{array}\right)+\left(\begin{array}{c}k\\ j+1\end{array}\right)=\left(\begin{array}{c}k+1\\ j+1\end{array}\right).$$

(2)

Lemma 2 

([14]). (Chu–Vandermonde’s Identity)). Let k, t and j be three integers. We have

$$\sum _{i=0}^j\left(\begin{array}{c}k\\ i\end{array}\right)\left(\begin{array}{c}t\\ j-i\end{array}\right)=\left(\begin{array}{c}k+t\\ j\end{array}\right).$$

(3)

3. Quadratic Functions

This section introduces a new class of quadratic functions, which is going to be utilized to construct the following WPB functions.

Let $f_m$ be a $2^m$-variable Boolean function with the form defined as

$$\begin{array}{cc}\hfill f_m(x_1,x_2,\cdots ,x_{2^{\mathrm{m}}})=& x_1\oplus x_2\oplus \cdots \oplus x_{2^{m-1}}\hfill \\ \hfill & \oplus x_1{x}_{1+2^{m-2}}\oplus x_2{x}_{2+2^{m-2}}\oplus \dots \oplus x_{2^{m-1}}{x}_{2^{m-1}+2^{m-2}},\hfill \end{array}$$

(4)

where $m\ge 2$, $f_1=x_1$.

Example 1. 

If $m=2$, $f_2\left(x_1,x_2,x_3,x_4\right)=x_1\oplus x_2\oplus x_1{x}_2\oplus x_2{x}_3$.

If $m=3$, $f_3\left(x_1,x_2,\dots ,x_8\right)=x_1\oplus x_2\oplus x_3\oplus x_4\oplus x_1{x}_3\oplus x_2{x}_4\oplus x_3{x}_5\oplus x_4{x}_6$.

Lemma 3. 

For $f_m\left(x\right)$ defined in (4), it follows that

$$f_m\left(x\right)=f_{m-1}\left(x^{\prime }\right)\oplus f_{m-1}\left(x^{″}\right),$$

where $x=\left(x_1,x_2,\dots ,x_{2^m}\right)$, $x^{\prime }=\left(x_1,x_3,\dots ,x_{2^m-1}\right)$, $x^{″}=\left(x_2,x_4,\dots ,x_{2^m}\right)$, and $m\ge 3$.

Proof. 

By (4), it can be deduced that

$$\begin{array}{cc}\hfill f_{m-1}\left(x^{\prime }\right)=& x_1\oplus x_3\oplus \cdots \oplus x_{2^{m-1}-1}\oplus \hfill \\ \hfill & x_1{x}_{1+2^{m-2}}\oplus x_3{x}_{3+2^{m-2}}\oplus \cdots \oplus x_{2^{m-1}-1}{x}_{2^{m-1}-1+2^{m-2}},\hfill \end{array}$$

and

$$\begin{array}{cc}\hfill f_{m-1}\left(x^{″}\right)=& x_2\oplus x_4\oplus \cdots \oplus x_{2^{m-1}}\oplus \hfill \\ \hfill & x_2{x}_{2+2^{m-2}}\oplus x_4{x}_{4+2^{m-2}}\oplus \cdots \oplus x_{2^{m-1}}{x}_{2^{m-1}+2^{m-2}}.\hfill \end{array}$$

Then, we obtain

$$\begin{array}{cc}\hfill f_{m-1}\left(x^{\prime }\right)\oplus f_{m-1}\left(x^{″}\right)=& x_1\oplus x_2\oplus \cdots \oplus x_{2^{m-1}}\hfill \\ \hfill & \oplus x_1{x}_{1+2^{m-2}}\oplus x_2{x}_{2+2^{m-2}}\oplus \cdots \oplus x_{2^{m-1}}{x}_{2^{m-1}+2^{m-2}}\hfill \\ \hfill =& f_m\left(x\right).\hfill \end{array}$$

□

By Lemma 3, we can easily know that $f_m\left(x\right)=1$ if and only if $f_{m-1}\left(x^{\prime }\right)\ne f_{m-1}\left(x^{″}\right)$, where $x^{\prime }$ and $x^{″}$ are defined as same as in Lemma 3. The p-weight support of $f_m$ in (4) can be derived from this fact, which is

$$\begin{array}{cc}\hfill {\mathrm{supp}}_p\left(f_m\right)=& \bigcup _{i=0}^p\left\{x\in {\mathbb{F}}_2^{2^m}\mid x^{\prime }\in {\mathrm{supp}}_i\left(f_{m-1}\right),x^{″}\in {\mathrm{zeros}}_{p-i}\left(f_{m-1}\right)\right\}\cup \hfill \\ \hfill & \bigcup _{i=0}^p\left\{x\in {\mathbb{F}}_2^{2^m}\mid x^{\prime }\in {\mathrm{zeros}}_i\left(f_{m-1}\right),x^{″}\in {\mathrm{supp}}_{p-i}\left(f_{m-1}\right)\right\}.\hfill \end{array}$$

(5)

Lemma 4. 

The p-weight of $f_m$ defined in (4) is

$${\mathrm{wt}}_p\left(f_m\right)=2\sum _{i=0}^p{\mathrm{wt}}_i\left(f_{m-1}\right)\left[\left(\begin{array}{c}{2}^{m-1}\hfill \\ p-i\hfill \end{array}\right)-{\mathrm{wt}}_{p-i}\left(f_{m-1}\right)\right],$$

(6)

where $1\le p\le 2^m-1$ and $m\ge 3$.

Proof. 

Assuming that $p-i=j$, from (5), we have

$$\begin{array}{cc}\hfill {\mathrm{supp}}_p\left(f_m\right)=& \bigcup _{i=0}^p\left\{x\in {\mathbb{F}}_2^{2^m}\mid x^{\prime }\in {\mathrm{supp}}_i\left(f_{m-1}\right),x^{″}\in {\mathrm{zeros}}_{p-i}\left(f_{m-1}\right)\right\}\cup \hfill \\ \hfill & \bigcup _{j=0}^p\left\{x\in {\mathbb{F}}_2^{2^m}\mid x^{\prime }\in {\mathrm{zeros}}_{p-j}\left(f_{m-1}\right),x^{″}\in {\mathrm{supp}}_j\left(f_{m-1}\right)\right\}\hfill \\ \hfill =& \bigcup _{i=0}^p\left\{x\in {\mathbb{F}}_2^{2^m}\mid x^{\prime }\in {\mathrm{supp}}_i\left(f_{m-1}\right),x^{″}\in {\mathrm{zeros}}_{p-i}\left(f_{m-1}\right)\right\}\cup \hfill \\ \hfill & \bigcup _{i=0}^p\left\{x\in {\mathbb{F}}_2^{2^m}\mid x^{″}\in {\mathrm{supp}}_i\left(f_{m-1}\right),x^{\prime }\in {\mathrm{zeros}}_{p-i}\left(f_{m-1}\right)\right\},\hfill \end{array}$$

where $x=\left(x_1,x_2,\dots ,x_{2^m}\right),x^{\prime }=\left(x_1,x_3,\dots ,x_{2^m-1}\right)$, and $x^{″}=\left(x_2,x_4,\dots ,x_{2^m}\right)$. Thus, we obtain

$${\mathrm{wt}}_p\left(f_m\right)=\left|{\mathrm{supp}}_p\left(f_m\right)\right|=2\sum _{i=0}^p{\mathrm{wt}}_i\left(f_{m-1}\right)\left[\left(\begin{array}{c}{2}^{m-1}\hfill \\ p-i\hfill \end{array}\right)-{\mathrm{wt}}_{p-i}\left(f_{m-1}\right)\right].$$

□

Lemma 5. 

Suppose m and p are two integers, then we have

$$\begin{array}{cc}\hfill & \sum _{\underset{(p-i) is even}{0\le i\le p}}\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)\frac{{(-1)}^{\frac{p-i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{p-i}{2}\end{array}\right)\hfill \\ \hfill =& \sum _{\underset{i is even}{0\le i\le p}}\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)\frac{{(-1)}^{\frac{i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{i}{2}\end{array}\right).\hfill \end{array}$$

(7)

Proof. 

Assuming that $p-i=j$, we have

$$\begin{array}{cc}\hfill & \sum _{\underset{(p-i) \mathrm{is} \mathrm{even}}{0\le i\le p}}\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)\frac{{(-1)}^{\frac{p-i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{p-i}{2}\end{array}\right)\hfill \\ \hfill =& \sum _{\underset{j \mathrm{is} \mathrm{even}}{0\le j\le p}}\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-j\end{array}\right)\frac{{(-1)}^{\frac{j}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{j}{2}\end{array}\right)\hfill \\ \hfill =& \sum _{\underset{i \mathrm{is} \mathrm{even}}{0\le i\le p}}\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)\frac{{(-1)}^{\frac{i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{i}{2}\end{array}\right).\hfill \end{array}$$

□

Theorem 1. 

The p-weight of $f_m$ defined in (4) is

$${\mathrm{wt}}_p\left(f_m\right)=\left\{\begin{array}{cc}\frac{1}{2}\left(\begin{array}{c}{2}^m\\ p\end{array}\right),\hfill & p\not\equiv 0(mod2),\hfill \\ \frac{1}{2}\left(\begin{array}{c}{2}^m\\ p\end{array}\right)-\frac{{(-1)}^{\frac{p}{2}}}{2}\left(\begin{array}{c}{2}^{m-1}\\ \frac{p}{2}\end{array}\right),\hfill & p\equiv 0(mod2),\hfill \end{array}\right.$$

(8)

where $1\le p\le 2^m-1$ and $m\ge 2$.

Proof. 

When $m=2$, the p-weights of $f_2\left(x_1,x_2,x_3,x_4\right)=x_1\oplus x_2\oplus x_1{x}_2\oplus x_2{x}_3$ in (4) are

$${\mathrm{wt}}_1\left(f\right)=\frac{1}{2}\left(\begin{array}{c}4\hfill \\ 1\hfill \end{array}\right)=2,{\mathrm{wt}}_2\left(f\right)=\frac{1}{2}\left(\begin{array}{c}4\hfill \\ 2\hfill \end{array}\right)+1=4,{\mathrm{wt}}_3\left(f\right)=\frac{1}{2}\left(\begin{array}{c}4\hfill \\ 3\hfill \end{array}\right)=2.$$

Thus, the p-weights of $f_2$ clearly satisfy (8).

The p-weights of the Boolean function $f_3\left(x_1,x_2,\dots ,x_8\right)=x_1\oplus x_2\oplus x_3\oplus x_4\oplus x_1{x}_3\oplus x_2{x}_4\oplus x_3{x}_5\oplus x_4{x}_6$ when $m=3$ in (4) are given in

Table 1. The p-weights of $f_3$ defined in (4).

p	1	2	3	4	5	6	7
${\mathrm{wt}}_p\left(f_3\right)$	4	16	28	32	28	16	4
$\frac{1}{2}\left(\begin{array}{c}8\\ p\end{array}\right)$	4	14	28	35	28	14	4

. It is easy to see that all the p-weights of $f_3$ satisfy (8).

Now, we will use mathematical induction to complete this proof. We first assume that (8) holds for $f_{m-1}$ when $m\ge 3$, i.e.,

$${\mathrm{wt}}_p\left(f_{m-1}\right)=\left\{\begin{array}{cc}\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p\end{array}\right),\hfill & p\not\equiv 0(mod2),\hfill \\ \frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p\end{array}\right)-\frac{{(-1)}^{\frac{p}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{p}{2}\end{array}\right),\hfill & p\equiv 0(mod2).\hfill \end{array}\right.$$

(9)

In what follows, we prove that (8) holds for $f_m$.

(1)

When p is a odd, it can be easily deduced that $p-i$ is even if i is odd, or that $p-i$ is odd if i is even. Then, we have

$$\begin{array}{cc}\hfill & {\mathrm{wt}}_p\left(f_m\right)\hfill \\ \hfill =& 2\sum _{i=0}^p{\mathrm{wt}}_i\left(f_{m-1}\right)\left[\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)-{\mathrm{wt}}_{p-i}\left(f_{m-1}\right)\right]\hfill \\ \hfill =& 2\sum _{\underset{i \mathrm{is} \mathrm{even}}{0\le i\le p}}\left[\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)-\frac{{(-1)}^{\frac{i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{i}{2}\end{array}\right)\right]\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)+\hfill \\ \hfill & 2\sum _{\underset{i \mathrm{is} \mathrm{odd}}{0\le i\le p}}\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)\left[\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)+\frac{{(-1)}^{\frac{p-i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{p-i}{2}\end{array}\right)\right]\hfill \\ \hfill =& 2\sum _{\underset{i \mathrm{is} \mathrm{even}}{0\le i\le p}}\left[\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)-\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)\frac{{(-1)}^{\frac{i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{i}{2}\end{array}\right)\right]+\hfill \\ \hfill & 2\sum _{\underset{i \mathrm{is} \mathrm{odd}}{0\le i\le p}}\left[\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)+\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)\frac{{(-1)}^{\frac{p-i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{p-i}{2}\end{array}\right)\right]\hfill \\ \hfill =& 2\sum _{i=0}^p\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)\hfill \\ \hfill =& \frac{1}{2}\left(\begin{array}{c}{2}^m\\ p\end{array}\right),\hfill \end{array}$$

where the first, second and fourth equations hold due to (6), (9) and (7), respectively, and the last one is from fact (3).

(2)

When p is even, we find that i is odd if $p-i$ is odd, or that i is even if $p-i$ is even. Then, we have

$$\begin{array}{cc}\hfill & {\mathrm{wt}}_p\left(f_m\right)\hfill \\ \hfill =& 2\sum _{i=0}^p{\mathrm{wt}}_i\left(f_{m-1}\right)\left[\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)-{\mathrm{wt}}_{p-i}\left(f_{m-1}\right)\right]\hfill \\ \hfill =& 2\sum _{\underset{i \mathrm{is} \mathrm{even}}{0\le i\le p}}\left[\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)-\frac{{(-1)}^{\frac{i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{i}{2}\end{array}\right)\right]\left[\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)+\frac{{(-1)}^{\frac{p-i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{p-i}{2}\end{array}\right)\right]\hfill \\ \hfill & +2\sum _{\underset{i \mathrm{is} \mathrm{odd}}{0\le i\le p}}\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)\left[\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)-\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)\right]\hfill \\ \hfill =& 2\sum _{\underset{i \mathrm{is} \mathrm{even}}{0\le i\le p}}\left[\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)-\frac{{(-1)}^{\frac{i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{i}{2}\end{array}\right)\frac{{(-1)}^{\frac{p-i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{p-i}{2}\end{array}\right)\right]\hfill \\ \hfill & +2\sum _{\underset{i \mathrm{is} \mathrm{odd}}{0\le i\le p}}\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)\hfill \\ \hfill =& 2\sum _{i=0}^p\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ i\end{array}\right)\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p-i\end{array}\right)-2\sum _{\underset{i \mathrm{is} \mathrm{even}}{0\le i\le p}}\frac{{(-1)}^{\frac{i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{i}{2}\end{array}\right)\frac{{(-1)}^{\frac{p-i}{2}}}{2}\left(\begin{array}{c}{2}^{m-2}\\ \frac{p-i}{2}\end{array}\right)\hfill \\ \hfill =& \frac{1}{2}\left(\begin{array}{c}{2}^m\\ p\end{array}\right)-\frac{{(-1)}^{\frac{p}{2}}}{2}\left(\begin{array}{c}{2}^{m-1}\\ \frac{p}{2}\end{array}\right),\hfill \end{array}$$

where the first, second and fourth equations hold due to (6), (9) and (7), respectively, and the last one is from fact (3).

□

4. WPB Functions

Let $h_m$ be a $2^m$-variable Boolean function, which can be defined as

$$h_m\left(x\right)=f_m\left(x\right)\oplus h_{m-1}\left(\overline{x}\right)\prod _{i=1}^{2^{m-1}}\left(x_i\oplus x_{2^{m-1}+i}\oplus 1\right),$$

(10)

where $m\ge 2$, $x=(x_1,x_2,\dots ,x_{2^m})\in {\mathbb{F}}_2^{2^m}$, $\overline{x}=(x_1,x_2,\dots ,x_{2^{m-1}})\in {\mathbb{F}}_2^{2^{m-1}}$, $h_1=x_1$, and $f_m\left(x\right)$ is defined in (4).

Example 2. 

It is clear that $h_1$ is WPB. When $m=2$, then

$$\begin{array}{c}\hfill h_2(x_1,x_2,x_3,x_4)=x_1\oplus x_2\oplus x_1{x}_2\oplus x_1{x}_3\oplus x_2{x}_3\oplus x_1{x}_2{x}_3\oplus x_1{x}_3{x}_4.\end{array}$$

The p-weight supports of $h_2$ are as follows,

$$\begin{array}{cc}\hfill & {\mathrm{supp}}_0\left(h_2\right)=⌀,\hfill \\ \hfill & {\mathrm{supp}}_1\left(h_2\right)=\{(1,0,0,0),(0,1,0,0)\},\hfill \\ \hfill & {\mathrm{supp}}_2\left(h_2\right)=\{(1,1,0,0),(0,1,0,1),(1,0,0,1)\},\hfill \\ \hfill & {\mathrm{supp}}_3\left(h_2\right)=\{(1,1,0,1),(1,0,1,1)\},\hfill \\ \hfill & {\mathrm{supp}}_4\left(h_2\right)=\left\{(1,1,1,1)\right\}.\hfill \end{array}$$

Thus, $h_2$ is WPB acoording the definition of WPB functions.

Lemma 6. 

Let $f_m$ be defined in (4). Given a vector $x=(x_1,x_2,\dots ,x_{2^m})\in {\mathbb{F}}_2^{2^m}$ such that $x_i=x_{2^{m-1}+i}$ for all $1\le i\le 2^{m-1}$, we have $f_m\left(x\right)=\mathrm{wt}\left(\overline{x}\right)(mod2)$, where $\overline{x}=(x_1,x_2,\dots ,x_{2^{m-1}})\in {\mathbb{F}}_2^{2^{m-1}}$.

Proof. 

$$\begin{array}{cc}\hfill & f_m\left(x\right)\hfill \\ \hfill =& x_1\oplus x_2\oplus \cdots \oplus x_{2^{m-1}}\oplus x_1{x}_{1+2^{m-2}}\oplus x_2{x}_{2+2^{m-2}}\oplus \cdots \oplus x_{2^{m-2}}{x}_{2^{m-1}}\hfill \\ \hfill & \oplus x_{2^{m-2}+1}{x}_{2^{m-1}+1}\oplus x_{2^{m-2}+2}{x}_{2^{m-1}+2}\oplus \cdots \oplus x_{2^{m-1}}{x}_{2^{m-1}+2^{m-2}}\hfill \\ \hfill =& x_1\oplus x_2\oplus \cdots \oplus x_{2^{m-1}}\oplus x_1{x}_{1+2^{m-2}}\oplus x_2{x}_{2+2^{m-2}}\oplus \cdots \oplus x_{2^{m-2}}{x}_{2^{m-1}}\hfill \\ \hfill & \oplus x_{2^{m-2}+1}{x}_1\oplus x_{2^{m-2}+2}{x}_2\oplus \cdots \oplus x_{2^{m-1}}{x}_{2^{m-2}}\hfill \\ \hfill =& x_1\oplus x_2\oplus \cdots \oplus x_{2^{m-1}}\hfill \\ \hfill =& \mathrm{wt}\left(\overline{x}\right)(mod2),\hfill \end{array}$$

where $\overline{x}=\{x_1,x_2,\dots ,x_{2^{m-1}}\}$. □

When $m\ge 2$, we note two facts: (1) the $2^m$-variable function ${\prod }_{i=1}^{2^{m-1}}\left(x_i\oplus x_{2^{m-1}+i}\oplus 1\right)$ takes 1 if and only if $x_i=x_{2^{m-1}+i}$ for all $1\le i\le 2^{m-1}$, and (2) $h_m=1$ if and only if $f_m\ne h_{m-1}{\prod }_{i=1}^{2^{m-1}}\left(x_i\oplus x_{2^{m-1}+i}\oplus 1\right)$. Therefore, we have come to the following conclusion.

Corollary 1. 

The p-weight support of Boolean function $h_m\left(x\right)$ defined in (10) is

$$\begin{array}{cc}\hfill {\mathrm{supp}}_p\left(h_m\right)=& {\mathrm{supp}}_p\left(f_m\right)\cup \left\{(\overline{x},\overline{x})\mid \overline{x}\in {\mathrm{supp}}_{\frac{p}{2}}\left(h_{m-1}\right)\right\}\hfill \\ \hfill & \setminus \left\{(\overline{x},\overline{x})\mid \overline{x}\in {\mathrm{supp}}_{\frac{p}{2}}\left(h_{m-1}\right),\mathrm{wt}\left(\overline{x}\right) is odd \right\},\hfill \end{array}$$

(11)

where $m\ge 2$, $x=(x_1,x_2,\dots ,x_{2^m})\in {\mathbb{F}}_2^{2^m}$, $\overline{x}\in {\mathbb{F}}_2^{2^{m-1}}$, $f_m\left(x\right)$ is defined in (4), and $1\le p\le 2^m-1$.

Theorem 2. 

$h_m$ defined in (10) is a weightwise perfectly balanced function.

Proof. 

We use mathematical induction on m in the proof process. First, by Example 2, we learn that $h_1$ and $h_2$ are WPB functions. Next, we assume that $h_{m-1}$ is a WPB function for $m\ge 3$ with $h_{m-1}\left(0_{m-1}\right)=0$ and $h_{m-1}\left(1_{m-1}\right)=1$. Thus, for $1\le p\le 2^{m-1}-1$,

$${\mathrm{wt}}_p\left(h_{m-1}\right)=\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ p\end{array}\right).$$

(12)

The calculation of the p-weight of $h_m\left(x\right)$ defined in (10) is divided into three specific cases according to the value of p.

(1)

If $p \mathrm{is} \mathrm{odd}$, we claim ${\prod }_{i=1}^{2^{m-1}}\left(x_i\oplus x_{2^{m-1}+i}\oplus 1\right)=0$, and then

$$\begin{array}{c}\hfill \begin{array}{c}\hfill {\mathrm{wt}}_p\left(h_m\right)={\mathrm{wt}}_p\left(f_m\right)=\frac{1}{2}\left(\begin{array}{c}{2}^m\\ p\end{array}\right),\end{array}\end{array}$$

where the last identity holds by Theorem 1.

(2)

If $p \mathrm{is} \mathrm{even}$, there is one case where there is an integer i such that $x_i$ is not equal to $x_{2^{m-1}+i}$. In this case, ${\mathrm{wt}}_p\left(h_m\right)=\frac{1}{2}\left(\begin{array}{c}{2}^m\\ p\end{array}\right)$, similarly to case (1). There is another case where the fact holds that $x_i=x_{2^{m-1}+i}$ for all $1\le i\le 2^{m-1}$. In this case, we will discuss the p-weight of $h_m\left(x\right)$ on the basis of the parity of $\frac{p}{2}$.

(2-1)

If $\frac{p}{2} \mathrm{is} \mathrm{odd}$, we claim

$$\begin{array}{cc}\hfill {\mathrm{wt}}_p\left(h_m\right)=& \left|x\in {\mathrm{supp}}_p\left(h_m\right)\right|\hfill \\ \hfill =& \left|{\mathrm{supp}}_p\left(f_m\right)\right|+\left|{\mathrm{supp}}_{\frac{p}{2}}\left(h_{m-1}\right)\right|-2\left|\left\{\overline{x}\in {\mathrm{supp}}_{\frac{p}{2}}\left(h_{m-1}\right)\mid \mathrm{wt}\left(\overline{x}\right) \mathrm{is} \mathrm{odd} \right\}\right|\hfill \\ \hfill =& \frac{1}{2}\left(\begin{array}{c}{2}^m\\ p\end{array}\right)-\frac{{(-1)}^{\frac{p}{2}}}{2}\left(\begin{array}{c}{2}^{m-1}\\ \frac{p}{2}\end{array}\right)+\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ \frac{p}{2}\end{array}\right)-2\times \frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ \frac{p}{2}\end{array}\right)\hfill \\ \hfill =& \frac{1}{2}\left(\begin{array}{c}{2}^m\\ p\end{array}\right),\hfill \end{array}$$

where $x\in {\mathbb{F}}_2^{2^m}$, $\overline{x}\in {\mathbb{F}}_2^{2^{m-1}}$. The second equality can be derived from Corollary 1, the third equality holds due to (8) and (12), and the last equality holds because $\frac{p}{2}$ is odd.

(2-2)

If $\frac{p}{2} \mathrm{is} \mathrm{even}$, we claim

$$\begin{array}{cc}\hfill {\mathrm{wt}}_p\left(h_m\right)=& \left|x\in {\mathrm{supp}}_p\left(h_m\right)\right|\hfill \\ \hfill =& \left|{\mathrm{supp}}_p\left(f_m\right)\right|+\left|{\mathrm{supp}}_{\frac{p}{2}}\left(h_{m-1}\right)\right|-2\left|\left\{\overline{x}\in {\mathrm{supp}}_{\frac{p}{2}}\left(h_{m-1}\right)\mid \mathrm{wt}\left(\overline{x}\right) \mathrm{is} \mathrm{odd} \right\}\right|\hfill \\ \hfill =& \frac{1}{2}\left(\begin{array}{c}{2}^m\\ p\end{array}\right)-\frac{{(-1)}^{\frac{p}{2}}}{2}\left(\begin{array}{c}{2}^{m-1}\\ \frac{p}{2}\end{array}\right)+\frac{1}{2}\left(\begin{array}{c}{2}^{m-1}\\ \frac{p}{2}\end{array}\right)\hfill \\ \hfill =& \frac{1}{2}\left(\begin{array}{c}{2}^m\\ p\end{array}\right),\hfill \end{array}$$

where $x\in {\mathbb{F}}_2^{2^m}$, $\overline{x}\in {\mathbb{F}}_2^{2^{m-1}}$. The second equation holds because of Corollary 1, the third equation is given by (8) and (12), and the last equation holds because of the condition that $\frac{p}{2}$ is even.

Now, we consider the vectors $0_{2^m}$ and $1_{2^m}$. It is easy to see that $h_m\left(0_{2^m}\right)=0$, and $h_m\left(1_{2^m}\right)=1$ since $f_m\left(1_{2^m}\right)=0$, $h_{m-1}\left(1_{2^{m-1}}\right)=1$.

Based on the above discussion, the result follows that $h_m\left(x\right)$ defined in (10) is a WPB function. □

Theorem 3. 

The algebraic degree of WPB function $h_m\left(x\right)$ defined in (10) is

$$\mathrm{deg}\left(h_m\right)=2^m-1.$$

Proof. 

Let the $2^m$-variable Boolean fuction $g_m\left(x\right)=h_{m-1}\left(\overline{x}\right){\prod }_{i=1}^{2^{m-1}}\left(x_i\oplus x_{2^{m-1}+i}\oplus 1\right)$, where $\overline{x}\in {\mathbb{F}}_2^{2^{\mathrm{m}-1}}$. Since $\mathrm{deg}\left(h_m\right)=max\{\mathrm{deg}\left(f_m\right),\mathrm{deg}\left(g_m\right)\}$, we can easily obtain $\mathrm{deg}\left(h_m\right)=\mathrm{deg}\left(g_m\right)$.

Based on the obvious fact that $\mathrm{deg}\left(h_1\right)=1$ and $\mathrm{deg}\left(h_2\right)=3$, we assume $\mathrm{deg}\left(h_{m-1}\right)=2^{m-1}-1$. Then, we have

$$\begin{array}{cc}\hfill & \mathrm{deg}\left(h_m\right)=\mathrm{deg}\left(g_m\right)=2^{m-1}-1+2^{m-1}=2^m-1.\hfill \end{array}$$

□

We simulate the p-weight nonlinearity of $h_3$ and $h_4$ using the computer program and compare them with existing WPB functions. As shown in

Table 2. The p-weight nonlinearity of known eight-variable WPB functions.

Functions	[7]	[8]	[9]	[11]	[10]	${\mathit{g}}_3$ in [13]	${\mathit{h}}_3$ in (10)	Upper Bound
${\mathrm{NL}}_2$	≤9	2	2	2	2	6	6	11
${\mathrm{NL}}_3$	≤22	12	14	12	12	8	17	24
${\mathrm{NL}}_4$	≤27	19	19	19	19	26	23	30
${\mathrm{NL}}_5$	≤22	12	14	12	12	8	17	24
${\mathrm{NL}}_6$	≤9	2	2	2	6	6	6	11

and

Table 3. The p-weight nonlinearity of known 16-variable WPB functions.

Function	${\mathrm{NL}}_2$	${\mathrm{NL}}_3$	${\mathrm{NL}}_4$	${\mathrm{NL}}_5$	${\mathrm{NL}}_6$	${\mathrm{NL}}_7$	${\mathrm{NL}}_8$	${\mathrm{NL}}_9$	${\mathrm{NL}}_{10}$	${\mathrm{NL}}_{11}$	${\mathrm{NL}}_{12}$	${\mathrm{NL}}_{13}$	${\mathrm{NL}}_{14}$
[8]	4	56	350	1312	3176	4782	5443	4782	3176	1312	350	56	4
[9]	4	112	686	1806	3436	4994	5603	4994	3436	1806	686	112	4
[11]	4	56	350	1288	3108	4774	5539	4902	3236	1672	654	152	28
[10]	4	56	350	1288	3108	4774	5539	4902	3228	1664	638	152	12
$h_4$ in (10)	12	104	590	1765	3487	5154	5827	5154	3491	1765	590	104	12
upper bound	54	268	888	2150	3959	5666	6378	5666	3959	2150	888	268	54

, the p-weight nonlinearity of $h_3$ and $h_4$ are close to the upper bound $⌊\frac{1}{2}\left(\begin{array}{c}n\\ p\end{array}\right)-\frac{1}{2}\sqrt{\left(\begin{array}{c}n\\ p\end{array}\right)}⌋$ and reach higher values than those of most existing functions. In addition, the p-weight nonlinearity of $h_4$ is the highest when p = 6, 7, 8, 9, 10.

In the end, the algebraic immunities of the function $h_m$ in (10) for m = 2, 3, 4 are given in

Table 4. The algebraic immunity of $h_m$ defined in (10), $m=2,3,4$.

m	$\mathrm{AI}\left({\mathit{h}}_{\mathit{m}}\right)$	Optimal Algebraic Immunity
2	$\mathrm{AI}\left(h_2\right)=2$	2
3	$\mathrm{AI}\left(h_3\right)=3$	4
4	$\mathrm{AI}\left(h_4\right)=3$	8

. Their algebraic immunrere is relatively poor when m takes the value 4. Therefore, we still need to make more efforts on the WPB function for the optimal algebraic immunity with high weightwise nonlinearity.

5. Conclusions

In this paper, we gave a class of new $2^m$-variable WPB functions and discussed the cryptographic properties of the new constructed WPB functions. We proved that their algebraic degree is $2^m-1$. The experimental results demonstrated that some of the p-weight nonlinearity of this class of WPB functions is higher than any currently known WPB functions for small m. Although the state-of-the-art studies regarding WPB functions show that the p-weight nonlinearity is difficult to prove theoretically, we still need to conduct more research to obtain the p-weight nonlinearity for large m in the future. In addition, while Boolean functions motivated by FLIP have attracted the attention of many researchers in recent years, there is little research on filter functions of b-FLIP (b instances of FLIP in parallel), which is also a direction worthy of study.