Bent functions linear on elements of some classical spreads and presemifields spreads

Abstract

Bent functions are maximally nonlinear Boolean functions with an even number of variables. They have attracted a lot of research for four decades because of their own sake as interesting combinatorial objects, and also because of their relations to coding theory, sequences and their applications in cryptography and other domains such as design theory. In this paper we investigate explicit constructions of bent functions which are linear on elements of spreads. After presenting an overview on this topic, we study bent functions which are linear on elements of presemifield spreads and give explicit descriptions of such functions for known commutative presemifields. A direct connection between bent functions which are linear on elements of the Desarguesian spread and oval polynomials over finite fields was proved by Carlet and the second author. Very recently, further nice extensions have been made by Carlet in another context. We introduce oval polynomials for semifields which are dual to symplectic semifields. In particular, it is shown that from a linear oval polynomial for a semifield one can get an oval polynomial for transposed semifield.

1 Introduction

Bent functions were introduced by Rothaus [26] in 1976 but already studied by Dillon [10] since 1974. A bent function is a Boolean function with an even number of variables which achieves the maximum possible nonlinearity. Bent functions have attracted a lot of research for four decades because of their relation to coding theory (in particular, as explained by Ding in the two nice papers [11, 12], bent functions give rise automatically to linear codes), sequences, applications in cryptography and other domains such as combinatorics and design theory.

Despite their simple and natural definition, bent functions turned out to admit a very complicated structure in general. On the other hand, many special explicit constructions are known. A jubilee survey paper on bent functions giving an historical perspective, and making pertinent connections to designs, codes and cryptography is [6]. A book devoted especially to bent functions and containing a complete survey (including variations, generalizations and applications) is [25].

Dillon [10] introduced bent functions related to partial spreads of $\mathbb {F}_{2^{m}} \times \mathbb {F}_{2^{m}}$. He constructed bent functions that are constant on elements of a spread. This approach was further studied in [16, 27]. Dillon also introduced a class H of bent functions that are linear on elements of a Desarguesian spread. With Carlet, the second author [5] has extended the class H into a more general class denoted by $\mathcal {H}$ and has shown that there is a one-to-one correspondence between these bent functions of $\mathcal {H}$ and the oval polynomials (o-polynomials) from finite geometry. In [4, 7] this approach was extended to other types of spreads. In particular the class $\mathcal {H}$ was generalized into $\mathcal {H}$-like by Carlet in [4] and bent functions which are affine on the elements of spreads were studied by the second author in [23] and next by Çeşmelioğlu et al. in [7]. Also, the reader notices that recently, bent vectorial functions have been derived from o-polynomials (see [26]).

In this paper we are interested in bent functions that are linear on elements of spreads. We firstly present in Section 3 an overview on explicit constructions of such bent functions and give a complete survey in this topic. Next, we investigate in Section 4 further generalizations of the class $\mathcal {H}$ by studying bent functions which are linear on the elements of spreads related to symplectic presemifields. We shall derive two explicit constructions and calculate their duals functions. In particular, we introduce a new type of o-polynomials for semifields which are dual to symplectic semifields. We also show that from a linear o-polynomial for a semifield one can get an o-polynomial for transposed semifield. It is well-known that the compositional inverse of o-polynomials for finite fields are again o-polynomials. We show that this fact is not true, in general, for finite semifields.

2 Preliminaries and notation

For any set E, E ^⋆=E∖{0} and # E denotes its cardinality.

2.1 Boolean and bent functions

Let $\mathbb {F}^{n}_{2}$ be the $\mathbb F_{2}$-vector space of dimension n. We shall endow $\mathbb {F}^{n}_{2}$ with the structure of field $\mathbb {F}_{2^{n}}$, the Galois field with 2ⁿ elements. A Boolean function on $\mathbb {F}_{2^{n}}$ is a mapping from $\mathbb {F}_{2^{n}}$ to the prime field $\mathbb {F}_{2}$. It can be represented as a polynomial in one variable $x\in \mathbb {F}_{2^{n}}$ of the form $f(x) ={\sum }_{j=0}^{2^{n}-1} a_{j} x^{j}$ where the a _j ’s are elements of the field. Such a function f is Boolean if and only if a ₀ and a ₂ ⁿ−1 belong to $\mathbb {F}_{2}$ and $a_{2j}={a_{j}^{2}}$ for every j∉{0,2ⁿ−1} (where 2j is taken modulo 2ⁿ−1). This leads to a unique representation which we call the polynomial form (for more details, see e.g. [3]). First, recall that for any positive integers k, and r dividing k, the trace function from $\mathbb {F}_{2^{k}}$ to $\mathbb {F}_{2^{r}}$, denoted by $Tr^{k}_{r}$, is the mapping defined for every $x\in \mathbb {F}_{2^{k}}$ as:

$$Tr_{r}^{k}(x):=\sum\limits_{i=0}^{\frac kr-1} x^{2^{ir}}=x+x^{2^{r}}+x^{2^{2r}}+\cdots+x^{2^{k-r}}. $$

In particular, we denote the absolute trace over ${\mathbb F}_{2}$ of an element $x \in {\mathbb F}_{2^{n}}$ by $Tr_{1}^{n}(x) = {\sum }_{i=0}^{n-1} x^{2^{i}}$. We make use of some known properties of the trace function such as $Tr^{n}_{1}(x)=Tr^{n}_{1}(x^{2})$ and for every integer r dividing k, the mapping $x\mapsto Tr^{k}_{r}(x)$ is $\mathbb {F}_{2^{r}}$-linear.

The bivariate representation of Boolean functions makes sense only when n is an even integer. It plays an important role for defining bent functions and is defined as follows: we identify $\mathbb {F}_{2^{n}}$ (where n=2m) with $\mathbb {F}_{2^{m}}\times \mathbb {F}_{2^{m}}$ and consider then the input to f as an ordered pair (x,y) of elements of $\mathbb {F}_{2^{m}}$. There exists a unique bivariate polynomial

$$\sum\limits_{0\leq i,j\leq 2^{m}-1}a_{i,j}x^{i}y^{j}$$

over $\mathbb {F}_{2^{m}}$ such that f is the bivariate polynomial function associated to it. Then the algebraic degree of f equals $\max _{(i,j)\, |\, a_{i,j}\neq 0}(w_{2}(i)+w_{2}(j))$ (where w ₂(i) is the Hamming (or binary) weight of the unique representation of i, that is, the number of 1’s in its binary expansion).The function f being Boolean, its bivariate representation can be written in the (non unique) form $f(x,y)=Tr^{m}_{1}(P(x,y))$ where P(x,y) is some polynomial in two variables over $\mathbb {F}_{2^{m}}$. There exist other representations of Boolean functions not used in this paper (see e.g. [3]) in which we shall only consider functions in their bivariate representation.

The first derivative of a Boolean function f in the direction of $a\in \mathbb {F}_{2^{n}}$ is defined as $D_{a} f(x)=f(x)+f(x+a), x\in \mathbb {F}_{2^{n}}$. Its second derivative in the direction of $(a,b)\in \mathbb {F}_{2^{n}}\times \mathbb {F}_{2^{n}}$ is given by D _a D _b f(x)=f(x+a+b)+f(x+a)+f(x+b)+f(x) where $x\in \mathbb {F}_{2^{n}}$.

If f is a Boolean function defined on $\mathbb {F}_{2^{n}}$, then the Walsh Hadamard transform of f is the discrete Fourier transform of the sign function χ _f :=(−1)^f of f, whose value at $\omega \in \mathbb {F}_{2^{n}}$ is defined as follows:

$$\forall\omega\in\mathbb{F}_{2^{n}},\quad \widehat{\chi_{f}}(\omega) = \sum\limits_{x\in\mathbb{F}_{2^{n}}} (-1)^{f(x)+Tr^{n}_{1}(\omega x)}. $$

Bent functions can be defined in terms of the Walsh transform as follows.

Definition 1

Let n be an even integer. A Boolean function f on $\mathbb {F}_{2^{n}}$ is said to be bent if its Walsh transform satisfies $\widehat {\chi _{f}} f(a) = \pm 2^{\frac {n}{2}}$ for all $a \in \mathbb {F}_{2^{n}}$.

One of the fundamental classes of bent functions is the Maiorana-McFarland’s class which is defined over $\mathbb {F}_{2^{m}}\times \mathbb {F}_{2^{m}}$ by (2.1):

$$ f(x,y) = Tr^{m}_{1}(\phi(y)x) + g(y),\quad (x,y)\in\mathbb{F}_{2^{m}}\times\mathbb{F}_{2^{m}} , $$

(2.1)

where ϕ is a permutation from $\mathbb {F}_{2^{m}}$ to itself and g stands for a Boolean function on $\mathbb {F}_{2^{m}}$.

Definition 2

Boolean functions $f,g:\mathbb {F}_{2^{n}}\rightarrow \mathbb {F}_{2}$ are extended-affine equivalent (in brief, EA-equivalent) if there exist an affine permutation L of $\mathbb {F}_{2^{n}}$ and an affine function $\ell :\mathbb {F}_{2^{n}}\rightarrow \mathbb {F}_{2}$ such that g(x)=(f∘L)(x)+ℓ(x). A class of functions is complete if it is a union of EA-equivalence classes. The complete class of a set of functions C is the smallest possible complete class that contains C.

If Boolean functions f and g are EA-equivalent and f is bent then g is bent too.

Finally, given a bent function f over $\mathbb {F}_{2^{n}}$, we can always define its dual function, denoted by $\widetilde {f}$, when considering the signs of the values of the Walsh transform $\widehat {\chi _{f}}(x)$ ($x \in \mathbb {F}_{2^{n}}$) of f. More precisely, $\widetilde {f}$ is defined by the equation:

$$ (-1)^{\widetilde{f}(x)}2^{\frac{n}{2}}=\widehat{\chi_{f}}(x). $$

(2.2)

Due to the involution law the Fourier transform is self-inverse. Thus the dual of a bent function is again bent, and $\widetilde {\widetilde {f}}=f$.

2.2 Quasifields and (pre-)semifields

We endow $\mathbb {F}_{2^{n}}$ with a magma denoted by ⋆.

Definition 3

$(\mathbb {F}_{2^{n}}^{\star },\star )$ is a quasigroup if for every a and b in $\mathbb {F}_{2^{n}}^{\star }$, there exist unique elements x and y in $\mathbb {F}_{2^{n}}^{\star }$ such that a⋆x=b and y⋆a=b.

Definition 4

$(\mathbb {F}_{2^{n}}^{\star },\star )$ is a loop if it is a quasigroup and there exist an identity element e such that e⋆a=a⋆e=a for every $a\in \mathbb {F}_{2^{n}}$.

Definition 5

$(\mathbb {F}_{2^{n}},+,\star )$ is a left quasifield (resp. left prequasifield) if

• 1. $(\mathbb {F}_{2^{n}},+)$ is an abelian group;

• 2. $(\mathbb {F}_{2^{n}}^{\star },\star )$ is a loop (resp. quasigroup);

• 3. For every a, b and c in $\mathbb {F}_{2^{n}}$, a⋆(b+c)=a⋆b+a⋆c (left distributivity);

• 4. 0⋆x=0 for every $x\in \mathbb {F}_{2^{n}}$.

In a right quasifield, we have the right distributivity instead of the left distributivity .

Definition 6

$(\mathbb {F}_{2^{n}},+,\star )$ is a semifield (resp. presemifield) if it is both a left and right quasifield (resp. prequasifield).

Hence, a presemifield is a semifield if it has a multiplicative identity.

One can define a presemifield S by considering elements of a finite field $\mathbb {F}_{2^{m}}$ and introducing a new multiplication operation ⋆ :

$$x\star y = xy + \sum\limits_{i < j}a_{ij}(x^{2^{i}}y^{2^{j}} + x^{2^{j}}y^{2^{i}}).$$

The classification of finite fields was done by Moore in 1893 but finite semifields are not classified yet.

Note that there exists a correspondence between presemifileds and the translation planes done by Lenz-Barlotti (http://www.math.uni-kiel.de/geometrie/klein/math/geometry/barlotti.html). An excellent reference on (partial-) spreads and related topics (such as Finite Geometries [8]) can be found in the book [13].

Definition 7

Two presemifields (S,+,⋆) and $(S^{\prime },+,\circ )$ are said to be isotopic if there exist three bijective linear mappings L, M, N from S to $S^{\prime }$ such that

$$L(x\star y) = M(x) \circ N(y),\forall x,y\in S;$$

If M=N then presemifields are called strongly isotopic.

We define a $\mathbb {F}_{2}$-bilinear form $B: \mathbb {F}_{2^{m}} \times \mathbb {F}_{2^{m}} \rightarrow \mathbb {F}_{2}$ by $B(x,y)=Tr^{m}_{1}(xy)$, and an alternating form on $( \mathbb {F}_{2^{m}} \times \mathbb {F}_{2^{m}} ) \times ( \mathbb {F}_{2^{m}} \times \mathbb {F}_{2^{m}} )$ by

$$\langle (x,y),(x^{\prime},y^{\prime}) \rangle = B(x,y^{\prime}) - B(y,x^{\prime}).$$

Let $S=( \mathbb {F}_{2^{m}} ,+,\star )$ be a presemifield with respect to operation ⋆. Then its dual presemifield $S^{d} = (\mathbb {F}_{2^{m}} +, \circ )$ is defined by operation

$$x \circ y = y\star x.$$

2.3 Spreads of $\mathbb {F}_{2^{n}}$

Partial spreads and spreads play an important role in some constructions of bent functions.

Definition 8

For a group G of order M ², a partial spread is a family S={H ₁,H ₂,⋯ ,H _N } of subgroups of order M which satisfies $H_{i}\cap H_{j}=\{0\}$ for all i≠j.

Definition 9

With the previous notation, if N=M+1 (which implies $\cup _{i=1}^{M+1} H_{i}=G$) then S is called a spread.

We will call the subgroups of a spread also spread elements. In the following, we shall consider the case where G is the additive group $(\mathbb {F}_{2^{n}},+)$ of the finite field $\mathbb {F}_{2^{n}}$ where n=2m is an even integer.

A general construction of spreads is given as follows. Let us consider a spread of $\mathbb {F}_{2^{n}}$ (where n=2m) whose 2^m+1 elements are the subspaces

$$\{(x,L_{z}(x)),x\in\mathbb{F}_{2^{m}}\},z\in\mathbb{F}_{2^{m}} $$

and

$$\{(0,y),y\in\mathbb{F}_{2^{m}}\} $$

where x↦L _z (x) is linear. The property of being a spread corresponds to the fact that for all $x\in \mathbb {F}_{2^{m}}^{\star }$ the mapping z↦L _z (x) is a permutation on $\mathbb {F}_{2^{m}}$.

Now, let us present some classical spreads of $\mathbb {F}_{2^{n}}$, where we identify $\mathbb {F}_{2^{n}}$ with $\mathbb {F}_{2^{m}} \times \mathbb {F}_{2^{m}}$.

• 1. The Desarguesian spreads: one considers the additive group $(\mathbb {F}_{2^{n}},+)$ of the finite field $\mathbb {F}_{2^{n}}$ with n=2m. Then two representations of the Desarguesian spreads are:

  • in $\mathbb {F}_{2^{n}}$ (univariate form): $\{u \mathbb {F}_{p^{n}}, u\in U\}$ where $U:=\{u\in \mathbb {F}_{p^{n}}\mid u^{p^{m}+1}=1\}$

  • in $\mathbb {F}_{2^{n}}\approx \mathbb {F}_{2^{m}} \times \mathbb {F}_{2^{m}}$ (bivariate form): $\{E_{a}, a\in \mathbb {F}_{2^{m}}\}\cup \{E_{\infty }\}$ where $E_{a}:=\{(x,ax)\, ;\, x\in \mathbb {F}_{2^{m}}\}$ and $E_{\infty }:=\{(0,y)\, ;\, y\in \mathbb {F}_{2^{m}}\}=\{0\}\times \mathbb {F}_{2^{m}}$.

• 2. The André spreads: there exist several generalizations of the Desarguesian spread. One of them leads to André’s spreads defined as follows:

  Let k be a divisor of m. Let ${{N_{k}^{m}}}$ be the norm map : ${{N_{k}^{m}}}$: $\mathbb {F}_{2^{m}} \rightarrow \mathbb {F}_{2^{k}}$, $x\mapsto {{N_{k}^{m}}} (x):=x^{\left (\frac {2^{m}-1}{2^{k}-1}\right )}$.

  Let Φ be any function ${\Phi } : \mathbb {F}_{2^{k}}\rightarrow \mathbb {Z}/(m/k)\mathbb {Z}$, $\phi ={\Phi }\circ {{N_{k}^{m}}}$. Then, the families ($\mathbb {F}_{2}$-vector spaces):

  $$\{\{(x,x^{2^{k\phi(z)}}z),x\in\mathbb{F}_{2^{m}}\},z\in\mathbb{F}_{2^{m}}\}$$

  and

  $$\{(0,y),y\in\mathbb{F}_{2^{m}}\}$$

  form together a spread of $\mathbb {F}_{2^{m}}\times \mathbb {F}_{2^{m}}$.

  This example which generalizes the Desarguesian spread has been introduced by J. André in the fifties and independently by Bruck later.

• 3. Spreads from quasifields and semifields: one can construct spreads via the quasifields and semifields. (In fact, every spread can be obtained from a, usually not unique, quasifield.) Let A ₀ be m×m zero matrix and A _s ($s\in \mathbb {F}_{2}^{m}\setminus \{0\}$), be invertible m×m-matrices over $\mathbb {F}_{2}$ such that A _r −A _s is invertible whenever r≠s. Such matrices induce a binary operation ⋆ on $\mathbb {F}_{2}^{m}$ defined by: x⋆s=x A _s . Thus, $(\mathbb {F}_{2}^{m},+,\star )$ is a right prequasifield (but the left distributive law in general does not hold).

  The subsets

  $$\{\{(x,x\star z),x\in \mathbb {F}_{2}^{m}\},z\in\mathbb {F}_{2}^{m}\} $$

  and

  $$\{(0,y),y\in\mathbb {F}_{2}^{m}\} $$

  form together a spread of $\mathbb {F}_{2}^{n}$ where n=2m.

Many examples of spreads based on quasifields are constructed with this manner: one can consider $(\mathbb {F}_{2^{m}},+,\star )$, where ⋆ is defined by x⋆z=L _z (x).

For instance, for André’s spreads, one considers $(\mathbb {F}_{2^{m}},+,\star )$ with $x\star z=L_{z}(x):=x^{2^{k\phi (z)}}z$.

Below, we present some classical prequasifields as well as the associate spreads.

• 1. Dempwolff-Muller pre-quasifield: assume k and m are odd integers with g c d(k,m)=1. Let e=2^m−1−2^k−1−1, $L(x) ={\sum }_{i=0}^{k-1} x^{2i}$ and define a multiplication in $\mathbb {F}_{2^{m}}$ as

  $$x\odot y= x^{e} L(xy).$$

  Endowed by the operation defined above, $(\mathbb {F}_{2^{m}}, +, \odot )$ becomes a prequasifield, called the Dempwolff-Muller pre-quasifield [9]. Such a prequasifield leads to the spread of the $\mathbb {F}_{2}$-vector subspaces $\{(0,y),y\in \mathbb {F}_{2^{m}}\}$ and $\{\{(x,z\odot x),x\in \mathbb {F}_{2^{m}}\}=\{(x,z^{e}L(xz)), x\in \mathbb {F}_{2^{m}}\}, z\in \mathbb {F}_{2^{m}}$.

• 2. The Knuth pre-quasifield: assume m is odd. For any $\beta \in \mathbb {F}_{2^{m}}^{\star }$, define a multiplication in $\mathbb {F}_{2^{m}}$ by

  $$x \odot y = xy + x^{2}Tr^{m}_{1} (\beta y) + y^{2}Tr^{m}_{1}(\beta x).$$

  Endowed by the operation defined above, $(\mathbb {F}_{2^{m}}, +, \odot )$ becomes a prequasifield, called the Knuth presemifield [21]. Such a presemifield gives rise to the spread of the $\mathbb {F}_{2}$-vector subspaces $\{(0,y), y\in \mathbb {F}_{2^{m}}\}$ and $\{\{(x,x\odot z),x\in \mathbb {F}_{2^{m}}\}=\{(x, zx+x^{2}Tr^{m}_{1}(\beta z)+z^{2}Tr^{m}_{1}(\beta x), x\in \mathbb {F}_{2^{m}}\}, z\in \mathbb {F}_{2^{m}}$.

• 3. The Kantor pre-semifield: assume m is odd. Define a multiplication in $\mathbb {F}_{2^{m}}$ by

  $$x\odot y =x^{2} y+Tr^{m}_{1} (xy)+ xTr^{m}_{1} (y). $$

  Endowed by the operation defined above, $(\mathbb {F}_{2^{m}}, +, \odot )$ becomes a presemifield, called the Kantor presemifield [15]. Such a presemifield leads to two spreads (two such spreads are sometimes called opposit of each other):

  • the spread of the $\mathbb {F}_{2}$-vector subspaces $\{(0,y),y\in \mathbb {F}_{2^{m}}\}$ and $\{\{(x,z\odot x), x\in \mathbb {F}_{2^{m}}\}=\{(x,z^{2} x+Tr^{m}_{1}(zx)+zTr^{m}_{1}(x)), x\in \mathbb {F}_{2^{m}}\}, z\in \mathbb {F}_{2^{m}}$.

  • the spread of the $\mathbb {F}_{2}$-vector subspaces $\{(0,y),y\in \mathbb {F}_{2^{m}}\}$ and $\{\{(x,x\odot z), x\in \mathbb {F}_{2^{m}}\}=\{(x,x^{2} z+Tr^{m}_{1}(xz)+xTr^{m}_{1} (z)), x\in \mathbb {F}_{2^{m}}\}, z\in \mathbb {F}_{2^{m}}$.

To a presemifield $S=(\mathbb {F}_{2^{m}}, +, \star )$, one can associate a spread, a collection of subspaces $\{ (0,y) \mid y \in \mathbb {F}_{2^{m}}\}$ and $\{ (x, x\star z) \mid m \in \mathbb {F}_{2^{m}} \}$, z∈F. Transpose presemifield $S^{t} =(\mathbb {F}_{2^{m}},+,\circ )$ of the presemifield S is defined as a presemifield whose associated spread is orthogonal (dual) to the spread of S with respect to the alternating form 〈⋅,⋅〉, that is,

$$\langle (x,x\star z),(y,y\circ z) \rangle = 0$$

for any $x, y, z \in \mathbb {F}_{2^{m}}$. It is equivalent to

$$B(x, y\circ z)=B(x\star z,y).$$

Definition 10

A presemifield $(\mathbb {F}_{2^{m}}, +, \circ )$ is called symplectic, if its associated spread is symplectic (that is, every subspace from spread is isotropic with respect to the alternating form 〈⋅,⋅〉). This means

$$0 = \langle (x,x \circ z),(y,y\circ z) \rangle = B(x, y\circ z)-B(x \circ z,y)$$

for any $x, y, z \in \mathbb {F}_{2^{m}}$. Equivalently,

$$ B(x,y \circ z) = B(x \circ z, y) $$

(2.3)

for any $x, y, z \in \mathbb {F}_{2^{m}}$.

Using operations S ^d and S ^t one can get at most 6 isotopy classes of presemifields, which is called the Knuth [20, 22] orbit $\mathcal {K}(S)$ of the presemifield S:

$$\mathcal{K}(S) = \{ [S],[S^{d}],[S^{t}],[S^{dt}],[S^{td}],[S^{dtd}]=[S^{tdt}]\}.$$

Definition 11

A presemifield $S=(\mathbb {F}_{2^{m}}, +, \star )$ is called commutative, if the operation ⋆ of multiplication is commutative. A presemifield S is commutative if and only if S=S ^d, and a presemifield S is symplectic if and only if S=S ^t.

Therefore, the Knuth orbit of a commutative (symplectic) presemifield contains at most three classes. If a presemifield S is commutative then S ^td is symplectic, and if S is symplectic then S ^dt is commutative. If a presemifield S is commutative then its transpose S ^t is dual to the symplectic presemifield S ^td.

For further details on symplectic spreads, we refer the reader to [1, 17–19].

Definition 12

If $L: \mathbb {F}_{2^{m}} \rightarrow \mathbb {F}_{2^{m}}$ is a $\mathbb {F}_{2}$-linear map, its adjoint operator L ^ad with respect to the form B is defined as a unique linear operator satisfying the following condition:

$$B(L(x),y)=B(x,L^{ad}(y)), \forall x,y \in \mathbb{F}_{2^{m}}.$$

Equality (2.3) means that all right multiplication mappings R _z (x)=x∘z of a symplectic presemifield are self-adjoint with respect to B.

Starting from a symplectic presemifield $(\mathbb {F}_{2^{m}}, +, \circ )$, one can construct a commutative presemifield in the following way [17, 19]. Consider the linear map $L_{z} : \mathbb {F}_{2^{m}} \rightarrow \mathbb {F}_{2^{m}}$, L _z (x)=z∘x. Let $L_{z}^{ad}$ be the adjoint operator of L _z with respect to the form B:

$$B(z\circ x, y) = B(L_{z}(x),y) = B(x, L_{z}^{ad}(y)). $$

We introduce a new operation ⋆ by

$$z\star y=L_{z}^{ad}(y). $$

Therefore,

$$B(z \circ x, y) = B(x, z \star y).$$

Then $(\mathbb {F}_{2^{m}} +, \star )$ is a commutative presemifield. Similarly, starting from commutative presemifield $(\mathbb {F}_{2^{m}}, +, \star )$ and putting L _z (x)=z⋆x, one can get a symplectic presemifield $(\mathbb {F}_{2^{m}} +, \circ )$:

$$B(z\star x, y) = B(L_{z}(x),y) = B(x, L_{z}^{ad}(y)) = B(x, z\circ y).$$

3 Bent functions linear on the elements of spreads

3.1 Bent functions linear on the elements of the Desarguesian spreads: the so-called class $\mathcal {H}$

In his thesis [10], Dillon introduced a class of bent functions denoted by H. Functions of the class H are defined in bivariate representation as

$$ f(x,y)=Tr^{m}_{1}(y+x\psi(yx^{2^{m}-2})), $$

(3.1)

where $x,y\in \mathbb {F}_{2^{m}}$ and ψ is a permutation of $\mathbb {F}_{2^{m}}$ such that ψ(x)+x does not vanish and for any $\beta \in \mathbb {F}_{2^{m}}^{\star }$, the function ψ(x)+β x is 2-to-1 (i.e. the pre-image of any element of $\mathbb {F}_{2^{m}}$ is either a pair or the empty set). The condition that ψ(x)+x does not vanish is required only for (3.1) to have a particular feature but is not necessary for bentness. Dillon was just able to exhibit bent functions in H that also belong to the completed Maiorana-McFarland class. In [5], Carlet and the second author have been extended the class H into a class denoted by $\mathcal {H}$ defined as follows.

Definition 13 (5)

The bent functions f of the class $\mathcal {H}$ are defined as

$$ f(x,y)=\left\{\begin{array}{ll}Tr^{m}_{1} \left(x\psi\left(\frac{y}{x}\right)\right)&\text{ if}\,\, x\neq 0\\ Tr^{m}_{1} \left(\mu y\right)&\text{ if}\,\, x=0 \end{array}\right. $$

(3.2)

where $\mu \in \mathbb {F}_{2^{m}}$ and ψ is a mapping from $\mathbb {F}_{2^{m}}$ to itself satisfying the following conditions:

$$ G:=\psi(z)+\mu z \text{ is a permutation on} \,\,\mathbb{F}_{2^{m}} $$

(3.3)

$$ \text{For every} \,\,\beta\in \mathbb{F}_{2^{m}}^{\star} ,\text{ the function}\,\, z\mapsto G(z)+\beta z \text{ is 2-to-1 on}\,\, \mathbb{F}_{2^{m}}. $$

(3.4)

Note that Condition (3.2) expresses the fact that functions f of the class $\mathcal {H}$ are linear on the elements of the Desarguesian spreads, while Conditions (3.3) and (3.4) express the bentness property of f. But it has been proven in [5] that Condition (3.4) implies Condition (3.3) and is necessary and sufficient for f being bent. Functions in $\mathcal {H}$ and in the Dillon class H are the same up to the addition of a linear term (namely, the term $Tr^{m}_{1}( (\mu +1)y)$). Any mapping G on $\mathbb {F}_{2^{m}}$ that satisfies Condition (3.4) is called an oval polynomial (in brief, “o-polynomial”).

3.2 Bent functions linear on the elements of other spreads: $\mathcal {H}$-like functions

In the line of the generalization done by Wu [27] of the well-known class Partial Spread $\mathcal {P}\mathcal {S}$ ¹ of Dillon into class $\mathcal {PS}$-like, the class $\mathcal {H}$ has been also generalized by Carlet in [4] into class $\mathcal {H}$-like by considering other spreads.

We recall the construction of bent functions from [4]. Let $L_{z} : \mathbb {F}_{2^{m}} \rightarrow \mathbb {F}_{2^{m}}$ be a linear function for any $z \in \mathbb {F}_{2^{m}}$. Consider a spread whose elements are the subspace $\{ (0,y) \mid y \in \mathbb {F}_{2^{m}} \}$ and 2^m subspaces $\{ (x,L_{z}(x)) \mid x \in \mathbb {F}_{2^{m}} \}$. We have seen that these subspaces form a spread if and only if the mapping z↦L _z (x)=y is a permutation of $\mathbb {F}_{2^{m}}$ for any nonzero $x \in \mathbb {F}_{2^{m}}$. Denote by Γ _x the compositional inverse of the permutation L _z (we have Γ _x (y)=z). A Boolean function on $\mathbb {F}_{2^{m}} \times \mathbb {F}_{2^{m}}$ is linear on the elements of the spread if and only if there exists a function $G: \mathbb {F}_{2^{m}} \rightarrow \mathbb {F}_{2^{m}}$ and an element $\mu \in \mathbb {F}_{2^{m}}$ such that, for every $y \in \mathbb {F}_{2^{m}}$,

$$ f(0,y) = Tr^{m}_{1} (\mu y), $$

(3.5)

and for every $x, z \in \mathbb {F}_{2^{m}}$,

$$ f(x,L_{z}(x)) = Tr^{m}_{1} (G(z)x). $$

(3.6)

Up to EA-equivalence, one can assume that μ=0. Indeed, one can add the linear function $g(x,y)=Tr^{m}_{1}(\mu y)$ to f; this changes μ into 0 and G(z) into $G(z)+L_{z}^{ad}(\mu )$, where $L_{z}^{ad}$ is the adjoint operator of L _z , since for y=L _z (x) one has $Tr^{m}_{1} (\mu y) = B(\mu , y) = B(\mu , L_{z}(x)) = B(L_{z}^{ad}(\mu ),x) = Tr^{m}_{1} (L_{z}^{ad}(\mu )x)$.

We take μ=0 in Expression (3.5), and Relation (3.6) becomes

$$ f(x,y) = Tr^{m}_{1} (G(z)x) = Tr^{m}_{1} (G({\Gamma}_{x}(y))x). $$

(3.7)

Theorem 1

([4]) Consider a spread of $\mathbb {F}_{2^{m}}\times \mathbb {F}_{2^{m}}$ whose elements are 2 ^m subspaces of the form $\{ (x,L_{z}(x)) \mid x \in \mathbb {F}_{2^{m}}\}$ , where, for every $z \in \mathbb {F}_{2^{m}}$ , function L _z is linear, and the subspace $\{ (0,y) \mid y \in \mathbb {F}_{2^{m}} \}$ . For every $x \in \mathbb {F}_{2^{m}}^{\ast }$ , let us denote by Γ _x the compositional inverse of the permutation L _z :z↦L _z (x)=y. A Boolean function defined by (3.7) is bent if and only if G is a permutation and, for every b≠0 the function $G(z) + L_{z}^{ad}(b)$ is 2-to-1, where $L_{z}^{ad}$ is the adjoint operator of L _z .

The case of the André’s spreads

Carlet [4] has applied the construction given by the previous theorem by considering the André’s spreads and deduced the related $\mathcal {H}$-like functions. Using the notation of Section 2.3, in the case of André’s spreads, L _z is given by $L_{z}(x)=x^{2^{k\phi (z)}}z$, ${\Gamma }_{x}(y)=\frac {y}{x^{2^{k\phi (y/x)}}}$, and $L_{z}^{ad}(b)=(bz)^{2^{m-k\phi (z)}}$. Consequently, Relation (3.7) becomes:

$$ f(x,y)=Tr^{m}_{1} \left(G\left(\frac{y}{x^{2^{k\phi (y/x)}}} \right) x \right), \forall x,y\in\mathbb{F}_{2^{m}}. $$

(3.8)

Functions of the form (3.8) are thus linear on the elements of the André’s spreads. Such functions f (with the convention $\frac {1}{0}=0$) are bent if and only if, G satisfies the following Conditions (3.9) and (3.10)

$$ z\mapsto G(z) \text{ is a permutation polynomial of}\,\, \mathbb{F}_{2^{m}}, $$

(3.9)

and

$$ z\mapsto G(z)+(bz)^{2^{m-k\phi(z)}} \text{ is 2-to-1 for every}\,\, b\in\mathbb{F}_{2^{m}}^{\star}. $$

(3.10)

Any polynomial that satisfies Conditions (3.9) and (3.10) is called a ϕ-polynomial. In particular, when ϕ is null, this notion corresponds to that of o-polynomials. Therefore, the class of bent functions of $\mathcal {H}$ gives rise to o-polynomial and the class of bent functions of $\mathcal {H}$-like gives rise to ϕ-polynomials.

The case of spreads based on prequasifields

Carlet [4] has applied the construction given by the previous theorem by considering some spreads based on prequasifields and deduced the related $\mathcal {H}$-like functions. In the following, we shall use the notation of Section 2.3.

• 1. In the case of the spread derived from the Dempwolff-Muller prequasifield, we have, ${\Gamma }_{x}(y)=\frac {1}{xD_{d}(\frac {y^{2}}{x^{2^{k}+1}})}$, where D _d is the Dickson polynomial of index the inverse d of 2^k−1 modulo 2ⁿ−1, and $L_{z}^{ad}(b)={\sum }_{i=0}^{k-1}(bz^{e})^{2^{-i}}z$. Consequently, Relation (3.7) becomes:

  $$ f(x,y)=Tr^{m}_{1} \left(G\left(\frac{1}{xD_{d}\left(\frac{y^{2}}{x^{2^{k}+1}}\right)}\right)x\right), \forall x,y\in\mathbb{F}_{2^{m}}. $$

  (3.11)

  Functions of the form (3.11) are thus linear on the elements of the the spread derived from the Dempwolff-Muller prequasifield. Such functions f are bent if and only if, G satisfies the following Conditions (3.12) and (3.13)

  $$ z\mapsto G(z) \text{ is a permutation polynomial of}\,\, \mathbb{F}_{2^{m}}, $$

  (3.12)

  and

  $$ z\mapsto G(z)+\sum\limits_{i=0}^{k-1}(bz^{e})^{2^{-i}}z \text{ is 2-to-1 for every}\,\, b\in\mathbb{F}_{2^{m}}^{\star}. $$

  (3.13)

• 2. In the case of the spreads derived from the Knuth presemifield, we have ${\Gamma }_{x}(y)= (1+Tr^{m}_{1}(\beta x))\frac {y}x+xTr^{m}_{1}(\beta \frac {y}x)+xTr^{m}_{1}(\beta x)C_{\frac {1}{\beta x}}(\frac {y}{x^{2}})$, where $\beta \in \mathbb {F}_{2^{m}}^{\star }$, $C_{a}(x)={\sum }_{i=0}^{m-1}c_{i}x^{2^{i}}$, with $c_{0}=\frac {1}{a^{2^{i}}}+\frac {1}{a^{3\cdot 2^{i}}}+\cdots +\frac {1}{a^{(m-3)\cdot 2^{i}}}$, $c_{i}=1+\frac {1}{a^{2^{i}}}+\frac {1}{a^{3\cdot 2^{i}}}+\cdots +\frac {1}{a^{(i-2)\cdot 2^{i}}}+\frac {1}{a^{(i+1)\cdot 2^{i}}}+\cdots +\frac {1}{a^{(m-1)\cdot 2^{i}}}$ if i odd and $c_{i}=1+\frac {1}{a^{2\cdot 2^{i}}}+\frac {1}{a^{4\cdot 2^{i}}}+\cdots +\frac {1}{a^{(i-2)\cdot 2^{i}}}+\frac {1}{a^{(i+1)\cdot 2^{i}}}+\cdots +\frac {1}{a^{(m-2)\cdot 2^{i}}}$ if i even. We have $L_{z}^{ad}(b)=bz+b^{2^{m-1}}Tr^{m}_{1}(\beta z)+\beta Tr^{m}_{1}(b^{2^{m-1}}z)$. Consequently, Relation (3.7) becomes:

  $$\begin{array}{@{}rcl@{}} f(x,y) &=& Tr^{m}_{1}\left(G\left(\left(1+Tr^{m}_{1}(\beta x)\right)\frac{y}x+xTr^{m}_{1}\left(\beta \frac{y}x\right)\right.\right. \\ && \left.\left. + xTr^{m}_{1}(\beta x)C_{\frac{1}{\beta x}}\left(\frac{y}{x^{2}}\right)\right)x\right), \forall x,y\in\mathbb{F}_{2^{m}}. \end{array} $$

  (3.14)

  Functions of the form (3.14) are thus linear on the elements of the spread derived from the Knuth presemifield. Such functions f are bent if and only if, G satisfies the following Conditions (3.15) and (3.16)

  $$ z\mapsto G(z) \text{ is a permutation polynomial of}\,\, \mathbb{F}_{2^{m}}, $$

  (3.15)

  and

  $$ z\mapsto G(z)+bz+b^{2^{m-1}}Tr^{m}_{1}(\beta x)+\beta Tr^{m}_{1}(b^{2^{m-1}}z) \text{ is 2-to-1 for every}\,\, b\in\mathbb{F}_{2^{m}}^{\star}. $$

  (3.16)

• 3. In the case of the spreads derived from the Kantor presemifield, there are two cases (since the Kantor presemifield leads to two spreads (see Section 2.3); the corresponding mapping Γ _x in the first case (resp. in the second case) was determined by Wu [27] and Carlet [4], respectively. Functions which are linear on the elements of the first spread derived from the Kantor presemifield are of the form

  $$\begin{array}{@{}rcl@{}} f(x,y)&=&Tr^{m}_{1}\left(G\left(\left((xy)^{2^{m-1}}+\sum\limits_{i=0}^{\frac{m-1}{2}}(xy)^{2^{2i}-1}+\sum\limits_{i=0}^{\frac{m-3}{2}}x^{2^{2i}} Tr^{m}_{1}(xy)\right)\frac{Tr^{m}_{1}(x)}{x}\right.\right.\\ &&\left.\left.+x^{2^{m-1}-1}y^{2^{m-1}}+x^{2^{m-1}-1}Tr^{m}_{1}(xy)\phantom{ \sum\limits_{i=0}^{\frac{m-3}{2}}}\right)x\right). \end{array} $$

  (3.17)

  Such functions f are bent if and only if, G satisfies the following Conditions (3.18) and (3.19)

  $$ z\mapsto G(z) \text{ is a permutation polynomial of}\,\, \mathbb{F}_{2^{m}}, $$

  (3.18)

  and

  $$ z\mapsto G(z)+bz^{2}+zTr^{m}_{1} (b)+Tr^{m}_{1}(bz) \text{ is 2-to-1 for every}\,\, b\in\mathbb{F}_{2^{m}}^{\star}. $$

  (3.19)

  Functions which are linear on the elements of the second spread derived from the Kantor presemifield are of the form

  $$\begin{array}{@{}rcl@{}} &&f(x,y)=Tr^{m}_{1}\!\left(\!G\!\left(\!\frac{y}{x^{2}}+Tr^{m}_{1} \!\left(\!\frac{1}{x}\!\right)\!\left(\!\frac{Tr^{m}_{1}\!\left(\!\frac{y}{x^{2}}\!\right)}{x^{2}} \,+\, \frac{Tr^{m}_{1}\!\left(\!\frac {y}{x}\!\right)}{x}\!\right) \,+\, \left(\!Tr^{m}_{1}\!\left(\!\frac{1}{x}\!\right) \,+\, 1 \!\right)\right.\right.\\ &&\qquad\qquad \times \left.\left.\left(\!\frac{Tr^{m}_{1}\!\left(\!\frac{y}{x^{2}}\!\right) \,+\, Tr^{m}_{1}\! \left(\!\frac {y}{x} \!\right)}{x^{2}} \,+\, \frac{Tr^{m}_{1}\! \left(\!\frac {y}{x^{2}}\!\right)}{x}\!\right)\!\right)\!x\!\right). \end{array} $$

  (3.20)

  Such functions f are bent if and only if, G satisfies the following Condition (3.21) and Condition (3.22)

  $$ z\mapsto G(z) \text{ is a permutation polynomial of}\,\, \mathbb{F}_{2^{m}}, $$

  (3.21)

  and

  $$ z\mapsto G(z)+(bz)^{2^{m-1}}+z Tr^{m}_{1} (b)+bTr^{m}_{1}(z) \text{ is 2-to-1 for every} \,\,b\in\mathbb{F}_{2^{m}}^{\star}. $$

  (3.22)

4 Bent functions linear on the elements of sympletic presemifields

Applying the class $\mathcal {H}$’s construction to a larger class of spreads gives more numerous $\mathcal {H}$-like bent functions which is interesting theoretically and may be useful for applications and developments (in particular in coding theory). In this section, we investigate further generalizations of the class $\mathcal {H}$ by studying bent functions which are linear on the elements of sympletic presemifields.

4.1 Two explicit constructions

We have seen in Section 3.2 that the construction of the class $\mathcal {H}$ has been extended by considering more general spreads. Unfortunately, no explicit construction of such polynomial G in Theorem 1 was provided.

By considering spreads based on symplectic presemifields, we derive from Theorem 1, an explicit construction of bent functions and we compute its dual function. To this end, we provide a mapping G satisfying the required conditions. We therefore answer to an open question addressed in [4].

Theorem 2

Let (F,+,∘) be a symplectic presemifield, and (F,+,⋆) be its corresponding commutative presemifield. Consider a spread of $\mathbb {F}_{2^{m}} \times \mathbb {F}_{2^{m}}$ whose elements are subspaces $\{ (0,y) \mid y \in \mathbb {F}_{2^{m}} \}$ and $\{ (x,z\circ x) \mid x \in \mathbb {F}_{2^{m}} \}$ , $z\in \mathbb {F}_{2^{m}}$ . For every $x \in \mathbb {F}_{2^{m}}^{\ast }$ , denote by Γ _x the inverse of the permutation z↦z∘x=y, and set G(z)=z⋆z. For every $c\in \mathbb {F}_{2^{m}}$ , let Z _c be the image of the map z↦z⋆(z+c), and χ _c be the characteristic function of the set Z _c ×{c}. Then a Boolean function defined by (3.7) is bent, and its dual function is

$$\tilde{f} = 1 + \sum\limits_{c \in \mathbb{F}_{2^{m}}} \chi_{c}. $$

Proof

We put L _z (x)=z∘x and use Theorem 1. We have to show that the equation

$$ G(z) + L_{z}^{ad}(b) =a $$

(4.1)

has 0 or 2 solutions in $\mathbb {F}_{2^{m}}$, for every $b\in \mathbb {F}_{2^{m}}^{\star }$, $a\in \mathbb {F}_{2^{m}}$. Since $L_{z}^{ad}(b) = z\star b$ and G(z)=z⋆z, the (4.1) becomes

$$z\star z + z\star b =a, $$

or

$$z\star (z+b)=a. $$

Denote

$$H_{b}(z)=G(z)+L_{z}^{ad}(b) = z\star z + z\star b.$$

We note that H _b (z) is a linear map (over $\mathbb {F}_{2}$), since the operation ∗ is commutative, and $\ker H_{b} = \{0,b\}$. Therefore, the equation H _b (z)=a has 0 or 2 solutions in F.

It remains to prove that G is a permutation. Suppose that the linear map G is not invertible. Then there exists $a\in \mathbb {F}_{2^{m}}^{\star }$ such that G(a)=0. Therefore a⋆a=0, a contradiction.

Now, we compute the dual function. The Walsh transform of the function f(x,y) is given by

$$\begin{array}{@{}rcl@{}} \widehat{\chi_{f}}(a,b) &=& \sum\limits_{x, y \in \mathbb{F}_{2^{m}}} (-1)^{f(x,y) + Tr^{m}_{1}( ax+by)} \\[-2pt] &=& \sum\limits_{x, y \in \mathbb{F}_{2^{m}}} (-1)^{Tr^{m}_{1} (G({\Gamma}_{x}(y))x + ax+by)} \\[-2pt] & = & 2^{m}\delta_{0}(b) + \sum\limits_{x \in \mathbb{F}_{2^{m}}^{*}, \ z \in \mathbb{F}_{2^{m}}} (-1)^{Tr^{m}_{1}(G(z)x + ax+bL_{z}(x))} \\[-2pt] & = & 2^{m}(\delta_{0}(b) -1) + \sum\limits_{z \in \mathbb{F}_{2^{m}} , \ x \in \mathbb{F}_{2^{m}}} (-1)^{Tr^{m}_{1} ((G(z) + a+L_{z}^{ad}(b))x)} \\[-2pt] & = & 2^{m}(\delta_{0}(b) -1 + \# \{ z \in \mathbb{F}_{2^{m}} , G(z) + a + L_{z}^{ad}(b) = 0\} ) \\[-2pt] & = & 2^{m}(\delta_{0}(b) -1 + \# \{ z \in \mathbb{F}_{2^{m}} , z\star z + z\star b = a \} ) \\[-2pt] & = & 2^{m} (-1)^{1 + {\sum}_{c \in \mathbb{F}_{2^{m}}} \chi_{c}}, \end{array} $$

which complete the proof. □

Denote R _x (z)=z∘x=y. Let ${\Gamma }_{x} = R_{x}^{-1}$ be the inverse function, so $z=R_{x}^{-1}(y)$. Let G(z)=z⋆z. Then the function from (3.7) can be rewritten as

$$ f(x,y) \,=\, Tr^{m}_{1} (G(z)x) \,=\, B(z\star z,x) \,=\, B(z, z\circ x) \,=\, B(z,y) \,=\, B({\Gamma}_{x}(y),y) \,=\, Tr^{m}_{1} (R_{x}^{-1}(y)y). $$

(4.2)

If the multiplication ⋆ in a commutative presemifield (F,+,⋆) is given by

$$x\star y = xy + \sum\limits_{i < j}a_{ij}\left(x^{2^{i}}y^{2^{j}} + x^{2^{j}}y^{2^{i}}\right), $$

then G(z)=z⋆z=z ².

Now we consider spreads of symplectic presemifields and prove a result similar to Theorem 2.

Theorem 3

Let $(\mathbb {F}_{2^{m}}, +, \circ )$ be a symplectic presemifield. Consider a spread of $\mathbb {F}_{2^{m}} \times \mathbb {F}_{2^{m}}$ whose elements are subspaces $\{ (0,y) \mid y \in \mathbb {F}_{2^{m}} \}$ and $\{ (x,x\circ z) \mid x \in \mathbb {F}_{2^{m}} \}$ , $z\in \mathbb {F}_{2^{m}}$ . For every $x \in \mathbb {F}_{2^{m}}^{*}$ , denote by Γ _x the inverse of the permutation z↦x∘z=y, and put $G(z)= \sqrt {z}$ . For every $c\in \mathbb {F}_{2^{m}}$ , let Z _c be the image of the map $z \mapsto \sqrt {z} + c\circ z$ , and χ _c be the characteristic function of the set Z _c ×{c}. Then a Boolean function defined by (3.7) is bent, and its dual function is

$$\tilde{f} = 1 + \sum\limits_{c \in \mathbb{F}_{2^{m}}} \chi_{c}.$$

Proof

Set L _z (x)=x∘z and use again Theorem 1. We have to show that the equation

$$G(z) + L_{z}^{ad}(b) = a$$

has 0 or 2 solutions in $\mathbb {F}_{2^{m}}$, for any nonzero $b \in \mathbb {F}_{2^{m}}$ and any $a \in \mathbb {F}_{2^{m}}$. It is equivalent to showing that

$$\dim \text{Im} \left(G(z) + L_{z}^{ad}(b)\right) = m-1, $$

since $G(z) + L_{z}^{ad}(b)$ is a linear function. Note that $L_{z}^{ad}(b) = L_{z}(b)$ since the right multiplication by z in a symplectic semifield is self-adjoint. Denote $M(z) = L_{z}^{ad}(b) = b\circ z$. Let $(\mathbb {F}_{2^{m}}, +, \star )$ be the commutative presemifield corresponding to the symplectic presemifield $(\mathbb {F}_{2^{m}}, +, \circ )$. Note that the adjoint function $L_{z}^{ad}(b)$ was calculated as adjoint of a function in b. Now we calculate the adjoint of $M(z) = L_{z}^{ad}(b)$ as function in z and show that M ^ad(z)=b⋆z. Indeed,

$$B(M^{ad}(z),x) = B(z,M(x)) = B(z,L_{x}^{ad}(b))= B(z, b\circ x) = B(b\star z,x).$$

We note that G ^ad(z)=z ² since

$$B(x,G^{ad}(z)) = B(G(x),z)= B(\sqrt{x},z) = Tr^{m}_{1}(\sqrt{x}z) = Tr^{m}_{1}(xz^{2}) = B(x,z^{2}).$$

Therefore,

$$(G(z) + M(z))^{ad} = G^{ad}(z) + M^{ad}(z) = z^{2} + b \star z. $$

Then

$$\begin{array}{@{}rcl@{}} \dim \text{Im} \left(G(z) + L_{z}^{ad}(b)\right) & = & \dim\text{Im} \left(G(z) + M(z)\right) \\ & = & \dim\text{Im} \left((G(z) + M(z))^{ad}\right)\\ & = & \dim \text{Im} (z^{2} + z\star b) \\ & = & m-1. \end{array} $$

Hence, the Boolean function defined by (3.7) is bent. Its dual (bent) function can be computed as in proof of Theorem 2. □

4.2 On oval polynomials for presemifields

In the following, we introduce the notion of an o-polynomial for a presemifield.

Definition 14

Let $S=(\mathbb {F}_{2^{m}},+,\star )$ be a presemifield. A mapping $G:\mathbb {F}_{2^{m}}\rightarrow \mathbb {F}_{2^{m}}$ is said to be an o-polynomial for S if G is a permutation and the function x↦G(x)+x⋆b is 2-to-1 function for any nonzero $b\in \mathbb {F}_{2^{m}}$.

Consider affine semifield plane $\{ (x,y) \mid x, y \in \mathbb {F}_{2^{m}}\}$. If G(x) is an o-polynomial then the “curve” y=G(x) intersects with the “line” y=x⋆b+a in one point if b=0, and 0 or 2 points if b≠0.

In the case of o-polynomial which are linear, one has the following result.

Theorem 4

Let $S=(\mathbb {F}_{2^{m}} +, \star )$ be a presemifield, and $S^{t}=(\mathbb {F}_{2^{m}} +, \circ )$ be its corresponding transpose presemifield. Let $G: \mathbb {F}_{2^{m}} \rightarrow \mathbb {F}_{2^{m}}$ be a linear o-polynomial for the presemifield S. Then the adjoint map G ^ad is an o-polynomial for the presemifield S ^t.

Proof

The mapping G ^ad is clearly a permutation. Define L _b (z)=z⋆b. Note that $L_{b}^{ad}(z) = z\circ b$ since

$$B(L_{b}^{ad}(z),x) = B(z, L_{b}(x)) = B(z,x\star b) = B(z\circ b,x) .$$

It is given that G(z)+z⋆b=G(z)+L _b (z) is a linear 2-to-1 function for any nonzero $b\in \mathbb {F}_{2^{m}}$. Hence

$$\dim \text{Im} (G(z) + L_{b}(z)) = m-1. $$

Now, we have

$$\begin{array}{@{}rcl@{}} \dim \text{Im} \left(G^{ad}(z) + z\circ b\right) & = & \dim \text{Im} \left(G^{ad}(z) + L_{b}^{ad}(z)\right) \\ & = & \dim\text{Im} \left((G(z) + L_{b}(z))^{ad}\right) \\ & = & \dim \text{Im} \left(G(z) + L_{b}(z)\right). \end{array} $$

Therefore, $\dim \text {Im} \left (G^{ad}(z) + z\circ b\right )=m-1$. Equivalently, z↦G ^ad(z)+z∘b is a 2-to-1 function for any nonzero $b\in \mathbb {F}_{2^{m}}$, which completes the proof. □

Example 1

Recall the construction of Kantor-Williams presemifields [17 , 18]. Let $F =\mathbb {F}_{2^{m}}$ with m>1 odd. Let $F=F_{0} \supset F_{1} \supset {\cdots } \supset F_{n}$ be a chain of subfields. For i∈{1,⋯ ,n}, denote by $T{r^{m}_{i}}$ the trace function from F to F _i . Let ζ _i ∈F ^∗. The commutative Kantor presemifield is given by operation

$$x\star y = xy + \left(x \sum\limits_{i=1}^{n} T{r^{m}_{i}}(\zeta_{i}y) + y \sum\limits_{i=1}^{n} T{r^{m}_{i}}(\zeta_{i} x) \right)^{2}, $$

and the corresponding Kantor-Williams symplectic presemifield is given by operation

$$x\circ y = xy + y^{2^{m-1}} \sum\limits_{i=1}^{n} T{r^{m}_{i}}(\zeta_{i}x) + \sum\limits_{i=1}^{n} \zeta_{i}T{r^{m}_{i}}(xy^{2^{m-1}} ).$$

By setting G(z)=z⋆z=z ², the function $f(x,y) = Tr^{m}_{1} ({\Gamma }_{x}(y)y)$ is bent. This expression is in implicit form, to make it explicit we have to find the explicit expression for Γ _x (y). Let us calculate Γ _x when the chain of subfields is of length 1, reduced to $F \supset F_{1}$ where $F_{1} = \mathbb {F}_{2^{k}}$. Set $T:=T{r^{m}_{k}}$ and ζ:=ζ ₁. Then

$$z\circ x = zx + \sqrt{x} T(\zeta z) + \zeta T(z \sqrt{x} ) =y,$$

$$z = \frac{y}{x} + \frac{\sqrt{x}}{x} T(\zeta z) + \frac{\zeta}{x} T(z \sqrt{x} ),$$

$$T(\zeta z) = T\left(\frac{\zeta y}{x}\right) + T\left(\frac{\zeta\sqrt{x}}{x}\right) T(\zeta z) + T\left(\frac{\zeta^{2}}{x}\right) T(z \sqrt{x} ),$$

$$T(z\sqrt{x}) = T\left(\frac{y\sqrt{x}}{x}\right) + T(\zeta z) + T\left(\frac{\zeta\sqrt{x}}{x}\right) T(z \sqrt{x} ).$$

Therefore, we obtain the following linear system:

$$\left\{ \begin{array}{rcrcl} \left(T\left(\frac{\zeta\sqrt{x}}{x}\right) +1\right) T(\zeta z) + T\left(\frac{\zeta^{2}}{x}\right) T(z \sqrt{x} ) & = & T\left(\frac{\zeta y}{x}\right) , \\ 1 \cdot T(\zeta z) + \left(T\left(\frac{\zeta\sqrt{x}}{x}\right) +1\right) T(z \sqrt{x} ) & = & T\left(\frac{y\sqrt{x}}{x}\right) . \end{array} \right. $$

The corresponding determinant equals $\left (T\left (\frac {\zeta \sqrt {x}}{x}\right ) +1\right )^{2} + T\left (\frac {\zeta ^{2}}{x}\right ) =1$. So

$$T(\zeta z) = T\left(\frac{\zeta y}{x}\right) \left(T\left(\frac{\zeta\sqrt{x}}{x}\right) +1\right) + T\left(\frac{y\sqrt{x}}{x}\right) T\left(\frac{\zeta^{2}}{x}\right), $$

$$T(z \sqrt{x}) = \left(T\left(\frac{\zeta\sqrt{x}}{x}\right) +1\right) T\left(\frac{y\sqrt{x}}{x}\right) + 1\cdot T\left(\frac{\zeta y}{x}\right). $$

Therefore,

$$\begin{array}{@{}rcl@{}} {\Gamma}_{x}(y)=z & = &\frac{y}{x} + \frac{\sqrt{x}}{x} \left(T\left(\frac{\zeta y}{x}\right) T\left(\frac{\zeta\sqrt{x}}{x}\right) +T\left(\frac{\zeta y}{x}\right) + T\left(\frac{y\sqrt{x}}{x}\right) T\left(\frac{\zeta^{2}}{x}\right) \right) \\ & & + \frac{\zeta}{x} \left(T\left(\frac{\zeta\sqrt{x}}{x}\right) T\left(\frac{y\sqrt{x}}{x}\right) +T\left(\frac{y\sqrt{x}}{x}\right) + T\left(\frac{\zeta y}{x}\right) \right). \end{array} $$

Let us give some remarks.

Remark 1

For finite fields endowed with the usual additive and multiplicative operations, an o-polynomial gives rise to a hyperoval in finite geometry. It is generally known that the function G(z)=z⋆z (from Theorem 2) gives rise to a hyperoval for commutative semifield planes (see, for example, [14]). The function $G(z)=\sqrt {z}$ (from Theorem 3) gives rise to hyperovals for semifields which are transpose to commutative semifields (and equivalently they are dual to symplectic semifields [17 , 19]).

Remark 2

Our computations show that for the case of Knuth [20] commutative presemifield $(\mathbb {F}_{2^{5}},+,\star )$, where the product is given by

$$x\star y = xy + x^{2} Tr^{5}_{1}(y) +y^{2} Tr^{5}_{1}(x), $$

the functions G ₁(z)=z ⁸, G ₂(x)=z+z ²+z ⁴ and G ₃(x)=z ²+z ⁴+z ⁸ give other examples of o-polynomials. The corresponding Kantor-Williams symplectic presemifield $(\mathbb {F}_{2^{5}},+,\circ )$ is given by operation

$$x\circ y = xy + y^{16} Tr^{5}_{1}(x) + Tr^{5}_{1}(xy^{16}).$$

Then by Theorem 4, the adjacent maps $G_{1}^{ad}(z)=z^{4}$, $G_{2}^{ad}(z)= z+ z^{8}+ z^{16}$ and $G_{3}^{ad}(z)= z^{4} + z^{8} + z^{16}$ give examples of o-polynomials for the transpose of Knuth presemifield, that is, the dual presemifield of the mentioned Kantor-Williams symplectic presemifield.

Remark 3

In the case of finite fields endowed with the usual operations, we know that if G(z) is an o-polynomial, then its compositional inverse G ⁻¹(z) is an o-polynomial as well (for instance, see [5]). However, we discover this fact is not true in general in the case of proper semifield, (that is, a finite semifield which is not a field). This means that G ⁻¹(z) might not to be o-polynomial neither for the semifield or its transpose. The previous Remark 2 provides examples of this fact.

The following result shows that linear o-polynomials G for presemifields lead to the construction of bent functions of type (3.7) from the completed Maiorana-McFarland class.

Proposition 1

Let $S=(\mathbb {F}_{2^{m}}, +, \circ )$ be a presemifield. Consider a spread of $\mathbb {F}_{2^{m}} \times \mathbb {F}_{2^{m}}$ whose elements are subspaces $\{ (0,y) \mid y \in \mathbb {F}_{2^{m}} \}$ and $\{ (x,z\circ x) \mid x \in \mathbb {F}_{2^{m}} \}$ , $z\in \mathbb {F}_{2^{m}}$ . For every $x \in \mathbb {F}_{2^{m}}^{*}$, denote by Γ _x the inverse of the permutation z↦z∘x=y. Let G(z) be a linear o-polynomial for the presemifield S. If a Boolean function f(x,y) defined by (3.7) is bent, then f belongs to the completed class of Maiorana-McFarland.

Proof

Recall that bent function f on $\mathbb {F}_{2^{n}}$ belongs to the completed Maiorana-McFarland’s class if and only if, there exists an n/2-dimensional subspace V for which the second derivative D _a D _b f(x)=f(x+a+b)−f(x+a)−f(x+b)+f(x)=0 for all a,b∈V (see e.g. [2 , 10]). To prove the result, we shall use the above notation and show that for $V =\{ (0,y) \mid y \in \mathbb {F}_{2^{m}} \}$ the second derivative D _(0,α) D _(0,β) f(x,y)=0 for all (0,α), (0,β)∈V. It is clear for x=0 since f(0,y)=0 for any $y \in \mathbb {F}_{2^{m}}$. Now, let x≠0, then by linearity of G and $R_{x}^{-1}$ (where $R_{x}^{-1}$ stands for the compositional inverse of R _x defined by R _x (z)=z∘x), we obtain

$$\begin{array}{@{}rcl@{}} D_{(0,\alpha)}D_{(0,\beta)}f(x,y) & = & f(x, y+\alpha+\beta) - f(x, y+\alpha) - f(x, y+\beta) + f(x, y) \\ & = & B(G(R_{x}^{-1}(y+\alpha+\beta)),x) - B(G(R_{x}^{-1}(y+\alpha)),x) \\ & & - B(G(R_{x}^{-1}(y+\beta)),x) + B(G(R_{x}^{-1}(y)),x) =0. \end{array} $$

□

4.3 An equivalence question

Firstly, recall that the notion of the so-called isotopism between two presemifileds.

Definition 15

Two presemifileds $(\hat {S}, +, \hat {\circ })$ and (S,+,∘) are called isotopic if there exist three bijective linear mappings L, M and N from $\hat {S}$ to S such that $L(x \hat {\circ } y) = M(x) \circ N(y), \forall x, y\in \hat {S}$.

In particular, if $S=\mathbb {F}_{2^{m}}$, then two presemifileds $(\mathbb {F}_{2^{m}},+,\hat {\circ })$ and $(\mathbb {F}_{2^{m}},+,\circ )$ are isotopic if $L(x \hat {\circ } y) = M(x) \circ N(y), \forall x, y\in \mathbb {F}_{2^{m}}$, for some linearized polynomials L, M and N on $\mathbb {F}_{2^{m}}$. Note that it is well-known that every presemifield is isotopic to a semifield.

In this subsection we consider a natural equivalence question. More precisely, we study whether we get EA-equivalent bent functions if we change semifield to an isotopic symplectic semifield. Let $\hat {S}=(\mathbb {F}_{2^{m}},+, \hat {\circ })$ and $S=(\mathbb {F}_{2^{m}},+, \circ )$ be two isotopic symplectic presemifields. Then there exist three bijective linear mappings L, M and N such that $L(x \hat {\circ } y) = M(x) \circ N(y), \forall x, y\in \mathbb {F}_{2^{m}}$. The presemifields S and $\hat {S}$ being symplectic, then B(x∘y,z)=B(x,z∘y) and $B(x \hat {\circ } y, z) = B(x, z \hat {\circ } y), \forall x,y,z\in \mathbb {F}_{2^{m}}$.

For the sake of readability, let us denote by $\bar {L}$ the adjoint operator of L (so that $\bar {L}:=L^{ad}$). Recall that an operator L is said to be self-adjoint if $\bar L=L$. With the above notation, we have

$$\begin{array}{@{}rcl@{}} B(L^{-1}(M(x) \circ N(y)), z) & = & B(x \hat{\circ} y, z) \\ & = & B(x, z \hat{\circ} y) \\ & = & B(x, L^{-1}(M(z) \circ N(y)) \\ & = & B(\bar{L}^{-1}(x), M(z) \circ N(y)) \\ & = & B(\bar{L}^{-1}(x) \circ N(y), M(z) ) \\ & = & B(\bar{M}(\bar{L}^{-1}(x) \circ N(y)), z ). \end{array} $$

Therefore, $L^{-1}(M(x) \circ N(y)) = \bar {M}(\bar {L}^{-1}(x) \circ N(y))$, that is, $M(x) \circ N(y) = L (\bar {M}(\bar {L}^{-1}(x) \circ N(y))).$ Denoting $\varphi = M \bar {L}$, $a=\bar {L}^{-1}(x)$, b=N(y), we have

$$\varphi(a) \circ b = \bar{\varphi} (a \circ b).$$

Let us denote by K ⁺(S) the set of endomorphisms φ of S (viewed as a vector space) such that $\varphi (a) \circ b = \bar {\varphi } (a \circ b)$ for every a,b∈S. Consequently, we proved the following statement.

Lemma 1

Let $S=(\mathbb {F}_{2^{m}},+, \circ )$ be a symplectic presemifield with respect to a form 〈⋅,⋅〉. Let $\hat {S}=(\mathbb {F}_{2^{m}},+, \hat {\circ })$ and S be isotopic presemifields with isotopism (M,N,L). Then $\hat {S}$ is symplectic with respect to the form 〈⋅,⋅〉 if and only if $M\bar {L} \in K^{+}(S)$.

We recall that the left nucleus of a semifield (S,+,∘) is defined as

$$N_{l}(S) = \{ c \in S \mid c \circ (x\circ y) = (c\circ x)\circ y \ \text{for \ all} \ x, y \in S\}.$$

Lemma 2

Let S be a symplectic semifield, c∈N _l (S), L _c (y)=c∘y. Then the map φ=L _c is self-adjoint with respect to the form B, that is, $\bar {\varphi } = \varphi$.

Proof

We have $B(x, \bar {\varphi }(y)) = B(\varphi (x),y) = B(c \circ x, y) = B(c, y\circ x) = B(c \circ (y\circ x),1) = B((c\circ y)\circ x,1) = B(c\circ y, x) = B(x,c\circ y)$. Hence $\bar {\varphi }(y) = c \circ y = \varphi (y)$, which completes the proof. □

An immediate consequence is the following.

Corollary 1

Let S be a symplectic semifield, c∈N _l (S), L _c (y)=c∘y. Then

$$K^{+}(S) \supseteq \{ L_{c} \mid c \in N_{l}(S) \}. $$

Proof

Let c∈N _l (S). We have $L_{c}(a)\circ b=(c\circ a)\circ b=c\circ (a\circ b)=L_{c}(a\circ b)=\bar {L}_{c}(a\circ b)$, according to Lemma 2. □

Now, let $(\mathbb {F}_{2^{m}}, +, \hat {\circ })$ and $(\mathbb {F}_{2^{m}},+,\circ )$ be two isotopic presemifields. Then there exist three linear permutations L, M and N of $\mathbb {F}_{2^{m}}$ such that $L(z\hat \circ x)=M(z)\circ N(x)$, for every $x,z\in \mathbb {F}_{2^{m}}$ (that is, $z \hat \circ x=L^{-1}(M(z)\circ N(x)), \forall x,z\in \mathbb {F}_{2^{m}}$). Let Γ (resp. $\hat {\Gamma }$) be the associate spread of $\mathbb {F}_{2^{m}} \times \mathbb {F}_{2^{m}}$ whose elements are subspaces $\{ (0,y) \mid y \in \mathbb {F}_{2^{m}} \}$ and $\{ (x,z \circ x) \mid x \in \mathbb {F}_{2^{m}}\}$, $z\in \mathbb {F}_{2^{m}}$ (resp. $\{ (0,y) \mid y \in \mathbb {F}_{2^{m}}\}$ and $\{ (x,z \hat \circ x) \mid x \in \mathbb {F}_{2^{m}} \}$, $z\in \mathbb {F}_{2^{m}}$). Let f (resp. $\hat f$) be a bent function which are linear on the elements of Γ (resp. $\hat {\Gamma }$), associated with the map G(z)=z⋆z=z ². The following result shows that in general functions f and $\hat {f}$ should not be EA-equivalent, but it does hold under a suitable assumption involving the linear permutations M and L, more precisely, $\bar M=L^{-1}$.

Corollary 2

Using the above notation, if $\bar M=L^{-1}$ then f and $\hat {f}$ are EA-equivalent bent functions.

Proof

We shall use the above notation. Since f (resp. $\hat f$) is linear on the elements of Γ (resp. $\hat {\Gamma }$), one has

$$f(x,y)=B(z\star z,x)=B(z,z\circ x)=B(z,y) = B(R_{x}^{-1}(y),y) \text{ and} \hat f(x,y)=B(z,z\hat\circ x).$$

Using the fact that

$$z \hat{\circ} x =L^{-1}(M(z)\circ N(x)) =y, \quad z=M^{-1}R_{N(x)}^{-1}L(y),$$

we get

$$\begin{array}{ll} \hat{f}(x,y)&=B(z,y)\\ & = B(M^{-1}R_{N(x)}^{-1}(L(y)),y)\\ & = B(R_{N(x)}^{-1}(L(y)), \bar{M}^{-1}(y))\\ & = B(R_{N(x)}^{-1}(L(y)), \bar{M}^{-1}L^{-1}(L(y)))\\ &=B(R_{N(x)}^{-1}(L(y)), (L\bar{M})^{-1}(L(y))). \end{array} $$

Therefore, if $\bar M=L^{-1}$, then

$$\hat{f}(x,y)=B(R_{N(x)}^{-1}(L(y)), L(y))=f(N(x),L(y))=(f\circ {\Phi}) (x,y),$$

where Φ:(x,y)↦(N(x),L(y)), proving that the bent functions f and $\hat {f}$ are EA-equivalent, which completes the proof. □

5 Conclusion

We firstly presented an overview on the study of bent functions linear on elements of classical spreads. Next, we pushed further the study initiated by Dillon [10] and extended by Carlet and the second author in [5] by introducing the class $\mathcal {H}$, and continued by Carlet in [4] very recently by introducing the class $\mathcal {H}$-like, to spreads related to (symplectic) presemifields and presented many developments in this direction. These studies provide more numerous $\mathcal {H}$-like bent functions which are interesting theoretically and may be useful for some applications, in particular in coding theory.