On a class of bent, near-bent, and 2-plateaued functions over finite fields of odd characteristic

1.   Introduction

Bent functions are extreme combinatorial objects with several areas of application, such as coding theory, maximum length sequences, cryptography, and the theory of difference sets to name a few. Boolean bent functions were introduced by Rothaus ^[6], who also considered two classes of bent functions. Among other equivalent characterizations of bent functions, the one that is most often used is a characterization of bent functions as a class of Boolean functions having so-called flat Walsh spectrum. It means that for any bent function over $GF(2)^n$, its Hamming distance to any affine function in $n$ variables is constant, including the distance to the all-zero function (or all-one function). The bent property of $f$ is commonly specified in terms of its flat Walsh spectrum, that is requiring that $W_f(\lambda) = \pm2^{n/2}$ for any $\lambda \in GF(2^n)$, where,

Here, $Tr_1^n:GF(2^n)\rightarrow GF(2)$ denotes the absolute trace function defined by $Tr_1^n(x) = x+x^2+\ldots + x^{2^{n-1}}$.

On the other hand, a generalization to finite fields of odd characteristic was first suggested in ^[3] and a function $f: GF(p^n)\rightarrow GF(p)$ is bent if and only if its Fourier transform defined by

is flat, that is, $|\widehat{f}(a)| = p^{n/2}$ for any $a \in GF(p^n)$. Here, $\omega = e^{\frac{2\pi \imath}{p}}$ denotes the primitive root of unity where $\imath = \sqrt{-1}$. Some surveys of known results on $p$-ary bent functions can be found in ^[1,3,5] and the references therein.

The classes of plateaued functions introduced by Zheng and Zhang ^[10] are good candidates for designing cryptographic functions since they possess various desirable cryptographic characteristics. They can be balanced for both odd and even number of variables, and they do not possess nonzero linear structures. In particular, the functions whose Fourier spectrum belong to $\{0, \pm p^{\frac{n+1}{2}}\}$ are known as near-bent functions and, they play a significant role in certain cryptographic primitives.

In 2016 and 2017, G. Xu et. al. ^[8,9] characterised the Fourier transform of the $p$-ary functions of the form

for the special case $p = 3$ and $n = 2k, \lambda\in GF(p^k)^*, u, v\in GF(p^n)^*$. The authors proved that some of these $p$-ary functions are also bent under certain conditions. Furthermore, a construction of quadratic ternary bent, near-bent and 2-plateaued functions from some known ternary bent functions are presented.

In this work we generalise the method for computing Fourier transform originally given in ^[8] for multinomial trace functions $f = f_{\lambda, u, v}:GF(p^n)\rightarrow GF(p)$ of the form $Tr_1^k(\lambda x^{p^k+1})+Tr^n_1(ux)Tr_1^n(vx)$ for any odd prime $p,$ where $n = 2k, \lambda\in GF(p^k)^*, u, v\in GF(p^n)^*.$ It is shown that the choice of $\lambda, u$ and $v$, ensuring that $f$ is bent, 2-plateaued or near-bent is directly related to finding the subset $A\subset GF(p)^3$ (cf. Section 4). Moreover, we give an efficient method for defining the set $A$ that corresponds for any odd prime $p$. This is not the case in the previous works, where the set $A$ is only explicitly defined just for the case $p = 3$.

The rest of this article is organized as follows. In Section 2 some basic definitions and notions are given. The analysis of the Fourier transform of the function $f$ is presented in Section 3. Some sufficient conditions for a given function to be bent, 2-plateaued and near-bent are derived in Section 4. Some concluding remarks are found in Section 5.

2.   Preliminaries

In the sequel, let ${\bf{F}}_{p^n}$ denote the finite Galois field $GF(p^n)$ consisting of $p^n$ elements. The group of units of ${\bf{F}}_{p^n}$, denoted by ${\bf{F}}_{p^n}^*$, is a cyclic group consisting of $p^n-1$ elements. An element $\alpha \in {\bf{F}}_{p^n}$ is said to be a primitive element if it is a generator of the multiplicative group ${\bf{F}}_{p^n}^*$. ${\bf{F}}_{p^n}$ is an $n$-dimensional vector space over ${\bf{F}}_p$. After fixing an ${\bf{F}}_p$-basis $(\gamma_0, \ldots, \gamma_{n-1})$ of ${\bf{F}}_{p^n}$, the mapping

defines an isomorphism of vector spaces over ${\bf{F}}_p$.

A bent function $f(x)$ is called regular if for every $a\in {\bf{F}}_{p^n}$ the normalized Fourier coefficient $p^{-\frac{n}{2}}\widehat{f}(a)$ equals to complex $p$-th root of unity, that is, $p^{-\frac{n}{2}}\widehat{f}(a) = \omega^{f^*(a)}$ where the function $f^*(a)$ is called the dual of $f(x).$ A binary bent function is always regular. For odd $p,$ a $p$-ary bent function $f(x)$ may not be regular, but its Fourier transform coefficients ^[3] satisfy

Such a function is called weakly regular, if for all $a\in {\bf{F}}_{p^n}$, $\imath$ is fixed.

If for all $a\in {\bf{F}}(p^n), \; \widehat{f}(a)\in \{0, \pm p^{\frac{n+s}{2}}\}$, where $0\leq s\leq n$, then a $p$-ary function $f(x)$ is called $s$-plateaued. In the case of $s = 1, \; f$ is called near-bent.

The trace function $Tr_k^n: {\bf{F}}_{p^n} \rightarrow {\bf{F}}_{p^k}$, a mapping to the subfield ${\bf{F}}_{p^k}$, where $k \mid n$, is defined as

3.   The Fourier coefficients of $f_{\lambda, u, v}$

Let $f_{\lambda, u, v}(x) = Tr_1^k(\lambda x^{p^k+1})+Tr^n_1(ux)Tr_1^n(vx)$, where $n = 2k, \lambda\in {\bf{F}}_{p^k}^{*}, u, v\in {\bf{F}}_{p^n}^{*}.$ In this section we compute the Fourier transform of the function $f(x)$ for any odd prime $p$. This result will help us to divide the class of functions $f_{\lambda, u, v}$ into subclasses of bent, near-bent and 2-plateaued functions.

Before we prove the main theorem we need the following preparatory result.

Lemma 1. ^[2,4] Let $n = 2k$ and $\lambda\in {\bf{F}}_{p^k}^{*}$. For any odd prime $p$, the p-ary monomial $g(x) = Tr_1^k(\lambda x^{p^k+1})$ is a weakly regular bent function. Moreover, for $a\in {\bf{F}}_{p^n}$ the corresponding Fourier transform coefficient of $g(x)$ is equal to

The authors in ^[8] computed the Fourier transform of the function $f_{\lambda, u, v}$ for $p = 3.$ In what follows, we continue the work of ^[8,9] and present the general form of the Fourier transform of $f_{\lambda, u, v}$ for any odd prime $p$.

Theorem 1. Let $n = 2k$ be a positive integer and $u, v\in {\bf{F}}_{p^n}^{*}.$ Define the function $f(x)$ by

where $g(x) = Tr_1^k(\lambda x^{p^k+1})$ is a $p$-ary function defined on ${\bf{F}}_{p^n}$. Then for any $a\in {\bf{F}}_{p^n}$, the corresponding Fourier transform coefficient of $f = f_{\lambda, u, v}$ is equal to

Proof. For $i, j = 0, \ldots, p-1$ and $u, v\in {\bf{F}}_{p^n}^*$ define the sets $T_i = \{x\in {\bf{F}}_{p^n} \mid Tr_1^n(ux) = i \}$ and denote

The Fourier transform coefficient of $f(x)$ at $a$ is equal to

Let us first compute $S_0(a)$. By definition of $T_i$ we have

Therefore, for any $b\in {\bf{F}}_p$ the Fourier transform of the function $g$ at the point $a+bu$ can be computed as

Since $\omega\in \mathbb{C}$ is a primitive $p$-root of unity, $1+\omega+\omega^2+\ldots + \omega^{p-1} = 0$. Hence, adding $p$ equations of (3.4) gives

Next we calculate $R_j(a-jv)$. Similar to the above, using the definition of $T_i$, we have

The last expression can be written in the matrix form as

where the coefficient matrix represents Discrete Fourier Transform (DFT) matrix. It is well-known that the inverse DFT matrix is

Therefore, we have

Then the desired conclusion follows from (3.5) and (3.6).

In what follows, we give explicit formulas for computing $S_0(a)$ and $R_j(a-jv)$ given by (3.5) and (3.6), respectively.

Let $g(x) = Tr_1^k(\lambda x^{p^k+1})$. According to (3.1) and using the fact $Tr_1^n(x) = Tr_1^k(Tr_k^n(x))$, we have

Denote $c_1 = Tr_1^n(\lambda^{-1}a^{p^k}u)$ and $t_1 = Tr_1^k(\lambda^{-1}u^{p^k+1})$. By (3.5) it follows

Since $\omega$ is a primitive $p$-th root of unity it holds $\omega^{p^k} = 1$, i.e., $\omega^{p^k+1} = \omega.$ Therefore

On the other side,

Denote $c_2 = Tr_1^n(\lambda^{-1}a^{p^k}v), \; t_2 = Tr_1^k(\lambda^{-1}v^{p^k+1})$ and $t_0 = Tr_1^n(\lambda^{-1}v^{p^k}u)$. By (3.6) it follows

In the next section we apply the above computation to construct some (near)-bent and 2-plateaued functions in the form of (3.2).

4.   Quadratic $p$-ary bent, near-bent and 2-plateaued functions

To make it easier construction of bent, near-bent and 2-plateaued functions, we are going to construct a subset $A$ of ${\bf{F}}_p^3, \; p > 3,$ which will help us to separate bent from non-bent functions. Its construction is described in the following way:

where $a_{ij}\in \{0, 1, \ldots, p-1\}$ and the boxed triples are fixed for any prime number $p$. The remaining coefficients $a_{ij}$ must satisfy the following conditions:

1. In each row, the product of the second and third numbers of a triple satisfies

2. The first $\frac{p-1}{2}$ rows are symmetric to the next $\frac{p-1}{2}$ rows in such a way that first and $(p-2)$ row, second and $(p-3)$, third and $(p-4)$, and so on, have the same second and third number of each triple.

3. In each column, the sum of the third numbers of a triple satisfies

Remark 1. Note that we have $p-1$ rows with $p-1$ triples, and the last row has $2p-1$ triples, which means that the cardinality of the subset $A$ is

Remark 2. The equation in third condition has more than one solution for any odd prime $p > 7$. In total, there is $(\frac{p-7}{2})! \cdot (\frac{p-7}{2})!$ possible solutions taking into account the first two conditions.

Example 1. Let us compute the set $A$ for $p = 11$. At the beginning we have

With the help of boxed triples and given conditions the remaining coefficients in the rows can be computed. For instance, in the first row, since $\frac{1}{4} \equiv 3 \mod 11$, we are solving the following equations

It is easy to see that $a_{02} = 7, a_{03} = 1, a_{04} = 9, a_{05} = 5, a_{06} = 6, a_{07} = 2, a_{08} = 10, a_{09} = 4, a_{010} = 8$. After other computations we get

With the help of third condition we can calculate the rest of the coefficients. In fact, we only need to solve the following equation

The possible solutions are $a_{21} = 5, a_{41} = 9$, or $a_{21} = 9, a_{41} = 5$, or $a_{21} = 8, a_{41} = 6$ or $a_{21} = 6, a_{41} = 8$. We can choose whatever solution we want. Therefore, for $a_{21} = 9$ and $a_{41} = 5$ we have

The following conjecture is the main result of this section and shows how the set $A$ defined above can be used in the construction of quadratic bent, near-bent and 2-plateaued functions. Unfortunately, we are unable to give a complete proof, for the following reasons: first, not all triples of the set $A$ are described in a general way, so we are not able to verify all triples, and second, the triples of ${\bf{F}}_p^3$ cannot be described in a way that is suitable for our proof technique. Therefore, we give a partial proof, and complete proof remains as an interesting problem for all mathematics enthusiasts.

Conjecture 1. Let $n = 2k$ with $k > 1$ and $\lambda\in {\bf{F}}_{p^k}^{*}, \; u, v\in {\bf{F}}_{p^n}^{*}$. Let the subset $A\subset {\bf{F}}_p^3$ be defined as in (4.1) and $f_{\lambda, u, v}(x)$ be a $p$-ary function defined as $f = f_{\lambda, u, v}(x) = Tr_1^k(\lambda x^{p^k+1})+Tr_1^n(ux)Tr_1^n(vx)$. Denote a triple $T = (Tr_1^n(\lambda^{-1}v^{p^k}u), Tr_1^k(\lambda^{-1}u^{p^k+1}), Tr_1^k(\lambda^{-1}v^{p^k+1}))$. Then

1. If $T\in {\bf{F}}_p^3\setminus A$, then $f$ is bent.

2. If $T\in A\setminus \{(p-1, 0, 0)\}$, then $f$ is near-bent.

3. If $T = (p-1, 0, 0)$, then $f$ is a 2-plateaued function.

Idea of Proof. Let us show the proof technique for the third statement. According to (3.7) and (3.8) we have

Then, using equation (3.3) we get

If $c_2 = 0$, then

If $c_1 = 0$, then $\widehat{f}(a) = -p^{k+1} \omega^{-Tr_1^k(\lambda^{-1}a^{p^k+1})}$, otherwise is 0.

If $c_2 \neq 0$, then $\widehat{f}(a) = 0.$

Therefore, $\vert \widehat{f}(a) \vert \in \{0, p^{k+1}\}$ for all $a\in {\bf{F}}_{p^n}$. Then $f$ is 2-plateaued.

This technique can also be used to prove either of the first two statements, but we are unable to check all possible triples.

Example 2. Let $p = 7$ and define the function $f(x) = Tr_1^k(\lambda x^{7^k+1})+Tr_1^n(ux)Tr_1^n(vx)$. By (4.1) we can define the set $A$ as

In what follows, we give some triples $(t_0, t_1, t_2)$ such that the function $f$ is bent, near-bent and 2-plateaued, respectively. It can be easily verified that for any $T\in {\bf{F}}_7^3 \setminus A$ the function $f$ is bent. For instance, if $T = (2, 3, 4)$, then

Similarly, for any $T\in A \setminus (6, 0, 0)$ the function $f$ is near-bent. For instance, if $T = (1, 1, 1)$, then

At the end, if $T = (6, 0, 0)$ then $f$ is 2-plateaued, i.e.,

5.   Conclusions

The exact computation of the Fourier transform for a given $p$-ary function of the form $f_{\lambda, u, v}$ has been established. Also, certain conditions such that a given $p$-ary function is bent, near-bent or 2-plateaued has been presented. It will be interesting to completely determine the distribution of the Fourier spectrum of these functions and try to determine the Fourier transform of the other $p$-ary functions using the presented method.

Acknowledgments

The research presented in this paper was financially supported by the Slovenian Research Agency under research program No. P2-0037 – Future Internet technologies: Concepts, architectures, services and socio-economic issues.

Conflict of interest

The author declares that he has no conflict of interest.