The nonlinearity and Hamming weights of rotation symmetric Boolean functions of small degree

1.   Introduction

Let $\mathbb{F}_2^n$ be the vector space of dimension $n$ over the two-element field $\mathbb{F}_2 = \{0, 1\}$. A Boolean function $f^n(x_0, \cdots, x_{n-1})$ in $n$ variables is a map from $\mathbb{F}_2^{n}$ to $\mathbb{F}_2$. Boolean functions have wide applications to different scientific areas, like information theory, electrical engineering, game theory, cryptography and coding theory. In 1999, Piepryzyk and Qu ^[8] introduced a kind of special Boolean functions such that their evaluations on every cyclic inputs are the same, which is called rotation symmetric Boolean functions (abbr. RSBFs). Further, Piepryzyk and Qu ^[8] showed that RSBFs are useful in the design of fast hashing algorithms with strong cryptographic properties. Since then, RSBFs have attracted much attention for their wide applications in cryptography and coding theory (^[2,5,9]).

For brevity, let the vectors $(x_0, x_1, ..., x_{n-1})$ and $(c_0, c_1, ..., c_{n-1})$ in $\mathbb{F}_2^n$ be denoted by $x^n$ and $c^n$ respectively. The Hamming weight of a function $f^n(x^n)$ is the number of $x^n \in \mathbb{F}_2^n$ satisfying $f^n(x^n) = 1$ and denoted by $wt(f^n)$. For any two $n$ variables Boolean functions $f^n(x^n)$ and $g^n(x^n)$, the Hamming distance between $f^n(x^n)$ and $g^n(x^n)$ is defined as $wt(f^n+g^n)$, and denoted by $d(f^n, g^n)$. We define the linear function $L_{c^n}$ by $L_{c^n}(x^n): = c^n\cdot x^n$, where $\cdot$ is the vector dot product. The nonlinearity of $f^n$ is defined as $N_{f^n}: = \min \{d(f^n, L_{c^n}) \mid c^n \in \mathbb{F}_2^n\}.$ Since hashing algorithm employing RSBFs with degree 2 as components cannot resist the linear and differential attacks ^[7], we need to use higher-degree RSBFs with high nonlinearity to protect from differential attack. As early as 1998, Filiol and Fontaine ^[4] studied the nonlinearity of RSBFs up to 9 variables. In this paper, we study the relation between Hamming weights and nonlinearity of RSBFs with small degree.

By $\left\langle{i}\right\rangle$ we denote the least nonnegative residue of $i \mod n$. Let $e$ and $l$ be integers such that $1\le e < n$ and $2\le l\le n$. Then the $l$-th rotation symmetric Boolean function $F_{l, e}^n$ in $n$ variables generated by the monomial $x_0x_ex_{\left\langle{2e}\right\rangle}...x_{\left\langle{(l-1)e}\right\rangle}$ is defined as

In 2009, Kim, Park and Hahn ^[6] explored the nonlinearity of $F_{2, e}^n$, and proved that if $\frac{n}{\gcd(n, e)}$ is even, then $N_{F_{2, e}^n} = wt(F_{2, e}^n)$, otherwise, $N_{F_{2, e}^n}\neq wt(F_{2, e}^n)$. In 2010, Ciungu ^[3] showed that the linearity of $F_{3, 1}^n$ is the same as its weight for the case $l = 3$ and $3|n$. Zhang, Guo, Feng and Li ^[11] totally proved the equality of the linearity of $F_{3, 1}^n$ and its weight. Later on, Yang, Wu and Hong ^[10] investigated the case $l = 4$ and proved that $wt(F_{4, e}^n) = N_{F_{4, e}^n}$. Furthermore, Yang, Wu and Hong ^[10] proposed the following conjecture.

Conjecture 1.1. ^[10] Let $e\ge 1$ and $l\ge 5$ be any given integer. Then the nonlinearity of $F_{l, e}^n$ is equal to its weight.

Recently, Castro, Medina and Stănică ^[2] showed that the Walsh transforms of symmetric and rotation symmetric Boolean functions satisfy the linear recurrence with integer coefficients, and suggested the following conjecture:

Conjecture 1.2. ^[2] Let $l > 1$ be a fixed integer. The sequence of $\{N_{F_{l}^i}\}_{i\ge l }$ satisfies the linear recurrence whose characteristic polynomial is given by

In this paper, we dedicate to prove that Conjecture 1.1 is true for some small degree cases, which also confirms Conjecture 1.2 for $l = 5, 6$ and 7. Particularly, we prove the following result.

Theorem 1.3. Let $l\in\{5, 6, 7\}$ and $e$ and $n$ be integers such that $1\le e < n$ and $n\ge 2l-1$. Then $N_{F_{l, e}^n} = wt(F_{l, e}^n).$

This paper is organized as follows. In Section 2, we study Fourier transform of Boolean functions and obtain some recursive formulas. In Section 3, we give the proof of Theorem 1.3. The final section is devoted to some remarks.

2.   Fourier transform of Boolean functions

We define the Fourier transform of the Boolean function $f^n(x^n)$ at $c^n \in \mathbb{F}_2^n$ to be

Obviously, we have $\widehat{f^n}\big(c^n\big) = 2^n-2wt(f^n+L_{c^n}).$ In particular, one has $\widehat{f^n}(0) = 2^n-2wt(f^n).$

First of all, we introduce some notations. We let $F_l^n: = F_{l, 1}^n$. Let $i', j'$ and $k'$ be nonnegative integers such that $1 \le k' \le j'-i'+1$. Let $m$ and $t$ be nonnegative integers such that $t\le m$. Let $X(i', j', 0): = 0$, $Y(m, 0): = 0$,

Let $n$ be an integer with $n\ge l$. Then we let

For any integers $i, j$ with $0\le i, j\le l-1$, we let

Now we let $n > l$. It is easy to check that if $x_{n-1} = 0$, then $t_{n} = t_{n-1}$ and $X(n-(l-1), n-1, i) = 0$ for any $0\leq i\leq l-1$. This implies that if $x_{n-1} = 0$, then

with $0\le i\le l-1$. If $x_{n-1} = 1$, then we derive that

Lemma 2.1. Let $l$ and $n$ be integers such that $n > l\ge 5$. Let $i$ and $j$ be integers such that $0 \le i, j \le l-1$. If $0\leq i\leq l-2$, then

If $i = l-1$, then

Proof. We only prove the relation $\widehat{f_{l-1, 0}^{n}}\big(c^n\big) = \widehat{f_{0, 0}^{n-1}}\big(c^{n-1}\big)-(-1)^{c_{n-1}}\widehat{f_{l-1, 0}^{n-1}}\big(c^{n-1}\big)$. The remaining relations can be handled similarly. It follows from (2.1) and (2.2) that

as desired. Thus Lemma 2.1 is proved.

Let $(c_{n-l+1}, c_{n-l+2}, \ldots, c_{n-1})\in \mathbb{F}_2^{l-1}$. If $n\ge 2l-1$, then $F_l^n$ can be written as

Now we let $(x_{n-l+1}, \cdots, x_{n-1})$ take all values in $\mathbb{F}_2^{l-1}$. If $l = 5$, then

If $l\ge 6$, then $\widehat{F_l^n}\big(c^n\big)$ can be decomposed as follows:

Now we let $c^n = (0, \cdots, 0)$. Clearly, we have $f_{i, j}^{n}(x_0, ..., x_{n-1}) = f_{j, i}^{n}(x_{n-1}, ..., x_0)$. Hence $\widehat{f_{i, j}^{n}}(0) = \widehat{f_{j, i}^{n}}(0)$. Thus we conclude that if $l = 5$, then

And if $l\ge 6$, then

Let $[x]$ denote the largest integer that is less than or equal to the real number $x$. In what follows, we give some recursive relations about $\widehat{f_{i, j}^{n}}(c^n)$ for any integer $i$ and $j$ with $0 \le i, j \le l-1$.

Lemma 2.2. Let $n, l, i, j$ and $k$ be integers such that $l\ge 5$, $n\ge 2l$, $0\leq i, j\leq l-1$ and $1\le k\le n$. Let $c^n = (c_0, ..., c_{n-1}) \in \mathbb{F}_2^n$ such that $c_{n-1} = 0$. Let $c^{k}$ be the vector consisting of the first $k$ bits of $c^n$. If $i = l-1$, then

If $i = l-2$, then

If $0\le i\le l-3$, then

Proof. Note that $c_{n-1} = 0$. We divide the proof into the following three cases.

Case 1. $i = l-1$. For any integer $j$ with $0\le j\le l-1$, by Lemma 2.1 we conclude that

If $l$ is even, then by Lemma 2.1 one derives that

If $l$ is odd, it then follows from Lemma 2.1 that

This finishes the proof of Lemma 2.2 in this case.

Case 2. $i = l-2$. Then by Lemma 2.1, we have

If $l$ is even, then one derives that

If $l$ is odd, then

Thus Lemma 2.2 is proved in this case.

Case 3. $0\le i\le l-3$. Then by Lemma 2.1, we have

Note that $0\le i\le l-3$. From Lemma 2.1 we derive that

If $i = 0$, then it is easy to see that $T_{n-(l-1)} = 2\widehat{f_{0, j}^{n-l}}\big(c^{n-l}\big).$ It follows from (2.5) that

If $i = 1$, then by (2.6) and Lemma 2.1, we have

Thus from (2.5), we obtain that

If $2\le i\le l-3$, then by (2.6) and Lemma 2.1, we have

Hence we obtain that if $i$ is odd, then

By (2.5), one deduces that

If $i$ is even, then

From (2.5) we derive that

Hence Lemma 2.2 holds in this case.

This completes the proof of Lemma 2.2.

Lemma 2.3. Let $n, l, i, j$ and $k$ be integers such that $l\ge5$, $n\ge 2l$, $0 \le i, j \le l-1$ and $1\le k\le n$. Let $c^n = (c_0, ..., c_{n-1}) \in \mathbb{F}_2^n$ such that $c_{n-1} = 1$. Let $c^{k}$ denote the first $k$ bits of $c^n$. Then

Proof. We divide the proof into the following three cases.

Case 1. $0\leq i\leq l-3$. Then by Lemma 2.1 we have

Thus Lemma 2.3 is true in this case.

Case 2. $i = l-2$. From Lemma 2.1 one deduces that

Hence Lemma 2.3 holds for this case.

Case 3. $i = l-1$. It follows from Lemma 2.1 that

If $l$ is even, then one derives that

as desired.

If $l$ is odd, then

as required. Hence Lemma 2.3 is proved in this case.

This finishes the proof of Lemma 2.3.

Lemma 2.4. Let $l, n, j$ be integers such that $l\ge 5$, $n \ge 2l$ and $0 \le j \le l-1$. Then for integer $i$ with $0\leq i\leq l-1$, we have

Proof. It follows from Lemma 2.2 that for any integer $j$ with $0\leq j\leq l-1$, we have

Thus (2.7) is true when $i = 0$ and $0\le j\le l-1$. Note that $\widehat{f_{i, j}^n}(0) = \widehat{f_{j, i}^n}(0)$. Then for $0\leq i\leq l-1$, one has

Then by the definition of $\widehat{f_{i, j}^n}(0)$ and the assumption $n \ge 2l-1$, we can conclude that (2.7) holds for any integer $0\le i, j\le l-1$. Hence Lemma 2.4 is proved.

In the following, we show that the weight of $F_l^n$ satisfies a linear recurrence, which is also proved by Castro, Chapman, Medina and Sep$\rm {\acute{u}}$lveda ^[1].

Proposition 2.5. Let $l$ and $n$ be integers such that $l\ge 5$ and $n \ge 2l$. Then

Proof. We only prove the case $l\ge 6$ since the case $l = 5$ can be done similarly. Let $l\ge 6$. It then follows from (2.4) and Lemma 2.4 that

Then by (2.4), we deduce that

The proof of Proposition 2.5 is complete.

Lemma 2.6 (Proposition 3.1, ^[10]). Let $f^n(x^n)$ be a Boolean function with $n$ variables. If $\widehat{f^n}(0) = \max \{ \big|\widehat{f^n}\big(c^n\big)\big| : c^n \in \mathbb{F}_2^n\},$ then $N_{f^n} = wt(f^n)$.

3.   Proof of Theorem 1.3

In this section, we show Theorem 1.3. For this purpose, we need the following lemma.

Lemma 3.1. Let $n$ and $l$ be nonnegative integers such that $5\le l\le 7$. Let $c^n = (c_0, \ldots, c_{n-1})\in \mathbb{F}_2^n$. If $c^n$ such that $c_1 = 1$, then for all $0\leq i, j\leq l-1$, we have

Proof. We prove Lemma 3.1 by induction on $n$. When $l\le n\le 2l-1$ and $c_1\neq 0$, using Maple 17 we can check that (3.1) holds for all $0\leq i, j\leq l-1$. For example, the case $l = n = 5$ is given in Table 1, we can check that $\widehat {f_{ij}^n}(c^5)\le \frac{1}{2^4}\widehat{F_l^{2l-1}}(0) = \frac{420}{2^4}$. In what follows, we let $n\ge 2l$. Assume that Lemma 3.1 holds for any positive integer $k$ less than $n-1$. Now we prove that Lemma 3.1 is true for the case $k = n$. Since $c_1 = 1$, we divide the proof into the following two cases.

Case 1. $c_{n-1} = 0$. From Lemma 2.2 and Theorem 2.5, then

Hence Lemma 3.1 is true in this case.

Case 2. $c_{n-1} = 1$. Then by Lemma 2.3 and Theorem 2.5 we have

Thus Lemma 3.1 holds for this case.

This finishes the proof of Lemma 3.1.

Now we present the proof of Theorem 1.3.

Proof of Theorem 1.3. From Lemma 2.6 we conclude that to prove the validity of Theorem 1.3 for $e = 1$, it suffices to prove that

From the definition of $F_{l}^{n}$, we conclude that for any integer $0\le j\le n-1$,

Without loss of generality, we suppose that $c_1\neq 0$. From Lemma 3.1, it follows that

It follows from (2.3) that $\widehat{F_{l}^{n}}(c^n)$ is the sum of $\widehat{f_{i, j}^{n-(l-1)}}(c^{n-(l-1)})$. Hence $\widehat{F_{l}^{n}}(c^n) < \widehat{F_{l}^{n}}(0)$. Namely, Theorem 1.3 is true for the case $e = 1$.

Now let $e > 1$. Let $s = \gcd(n, e)$ and $t = n/s$. Then

For $0\leq k\leq {s-1}, 0\leq j\leq {t-1}$, substituting $x_{\left\langle{k+je}\right\rangle}$ by $y_j^{(k)}$, one gets that

Let $c_k^t = (c_k, c_{\left\langle{e+k}\right\rangle}, ..., c_{\left\langle{(t-1)e+k}\right\rangle})$ and $x_k^t = (x_k, x_{\left\langle{e+k}\right\rangle}, ..., x_{\left\langle{(t-1)e+k}\right\rangle})$. For any $c_k^t\neq0$, we have showed that $\widehat{g_k^t}\big(c_k^t\big) < \widehat{g_k^t}(0).$ Then for all $c^n = (c_0, ..., c_{n-1}) \ne 0$, it follows from the definition of Fourier transform and (3.2) that

Thus Theorem 1.3 is true for the case $e > 1$.

This concludes the proof of Theorem 1.3.

4.   Final remarks

In Section 2, we present some recursive formulas for the Fourier transform of $f_{i, j}^n(x^n)$ and $F_{l}^n(x^n)$ for all positive integers $i, j, l$ and $n$ such that $l\ge 5$, $0\le i, j \le l-1$ and $n\ge 2l$. So to prove the truth of Conjectures 1.1 and 1.2, it is enough to show that for any integer $n$ such that $l\le n\le 2l-1$, the inequality

is true when $c_1 = 1$. When $l$ is an integer greater than 7 but not too large, by some direct calculations one can derive that (4.1) holds. But for the general case when $l > 7$, one meets some obstructions when one tries to prove (4.1). Hence we propose the following conjecture.

Conjecture 4.1. Let $i, j, l, n$ be integers such that $l > 7$, $l\le n\le 2l-1$ and $0\le i, j\le l-1$ and let $c^l = (c_0, \cdots, c_{l-1})\in \mathbb{F}_2^l$ with $c_1 = 1$. Then

Let $q = p^r$ with $p$ being a prime and $r > 1$. One can form the exponential sum of a function $F: \mathbb{F}_q^n\rightarrow \mathbb{F}_q$ as follows:

where ${\rm Tr}_{\mathbb{F}_q/\mathbb{F}_p}$ represents the field trace function from $\mathbb{F}_q$ to $\mathbb{F}_p$. Castro, Chapman, Medina and Sep$\rm {\acute{u}}$lveda ^[1] showed that the sequence of $\{S_{\mathbb{F}_q}{(F_{l}^n)}\}_{n\ge l }$ satisfies the linear recurrence whose characteristic polynomial is given by

On the other hand, by Lemma 2.4, we know that for any integer $i$ and $j$ with $0\leq i, j\leq l-1$, the sequence $\{S_{\mathbb{F}_2}{(f_{i, j}^n)}\}_{n\ge l}$ satisfies the linear recurrence whose characteristic polynomial is given by

We believe that the same holds for the general finite field. That is, we suggest the following conjecture as the conclusion of this paper.

Conjecture 4.2. Let $i, j$ and $l$ be integers with $l\ge 3$ and $0\le i, j \le l-1$. The sequence $\{S_{\mathbb{F}_q}{(f_{i, j}^n)}\}_{n\ge l}$ satisfies the linear recurrence whose characteristic polynomial is given by

Acknowledgments

The authors would like to thank the anonymous referees for careful reading of the manuscript and helpful comments and corrections that improved the presentation of this paper. Hong was supported partially by the Fundamental Research Funds for the Central Universities.

Conflict of interest

We declare that we have no conflict of interest.