Commutative Presemifields and Semifields

Background

For a prime $p$ and a positive integer $n$ let ${𝔽}_{p^n}$ be the finite field with $p^n$ elements. Let $F$ be a map from the finite field to itself. Such function admits a unique representation as a polynomial of degree at most $p^n-1$, i.e.

$F(x)=\sum _{j=0}^{p^n-1}{a}_j{x}^j,a_j\in {𝔽}_{p^n}$.

The function $F$ is

• linear if $F(x)=\sum _{j=0}^{n-1}{a}_j{x}^{p^j}$,
• affine if it is the sum of a linear function and a constant,
• DO (Dembowski-Ostrim) polynomial if $F(x)=\sum _{0\le i\le j<n}{a}_{ij}{x}^{p^i+p^j}$,
• quadratic if it is the sum of a DO polynomial and an affine function.

For $\delta$ a positive integer, the function $F$ is called differentially $\delta$-uniform if for any pairs $a,b\in {𝔽}_{p^n}$, with $a\ne 0$, the equation $F(x+a)-F(x)=b$ admits at most $\delta$ solutions.

A function $F$ is called planar or perfect nonlinear (PN) if ${\delta }_F=1$. Obviously such functions exist only for $p$ an odd prime. In the even case the smallest possible case for $\delta$ is two (APN function).

For planar function we have that the all the nonzero derivatives, $D_{a}F(x)=F(x+a)-F(x)$, are permutations.

Equivalence Relations

Two functions $F$ and $F^{\prime }$ from ${𝔽}_{p^n}$ to itself are called:

• affine equivalent if $F^{\prime }=A_1\circ F\circ A_2$, where $A_1,A_2$ are affine permutations;
• EA-equivalent (extended-affine) if $F^{\prime }=F^{″}+A$, where $A$ is affine and $F^{″}$ is afffine equivalent to $F$;
• CCZ-equivalent if there exists an affine permutation $ℒ$ of ${𝔽}_{p^n}\times {𝔽}_{p^n}$ such that $ℒ(G_F)=G_{F^{\prime }}$, where $G_F=\{(x,F(x)):x\in {𝔽}_{p^n}\}$.

CCZ-equivalence is the most general known equivalence relation for functions which preserves differential uniformity. Affine and EA-equivalence are its particular cases. For the case of quadratic planar functions the isotopic equivalence is more general than CCZ-equivalence, where two maps are isotopic equivalent if the corresponding presemifields are isotopic.

On Presemifields and Semifields

A presemifield is a ring with left and right distributivity and with no zero divisor. A presemifield with a multiplicative identity is called a semifield. Any finite presemifield can be represented by $𝕊=({𝔽}_{p^n},+,\star )$, for $p$ a prime, $n$ a positive integer, $𝕊=({𝔽}_{p^n},+)$ additive group and $x\star y$ multiplication linear in each variable. Every commutative presemifield can be transformed into a commutative semifield.

Two presemifields ${𝕊}_1=({𝔽}_{p^n},+,\star )$ and ${𝕊}_2=({𝔽}_{p^n},+,\circ )$ are called isotopic if there exist three linear permutations $T,M,N$ of ${𝔽}_{p^n}$ such that $T(x\star y)=M(x)\circ N(y)$, for any $x,y\in {𝔽}_{p^n}$. If $M=N$ then they are called strongly isotopic. Each commutative presemifields of odd order defines a planar DO polynomial and viceversa:

• given $𝕊=({𝔽}_{p^n},+,\star )$ let $F_{𝕊}(x)=\frac{1}{2}(x\star x)$;
• given $F$ let ${𝕊}_F=({𝔽}_{p^n},+,\star )$ defined by $x\star y=F(x+y)-F(x)-F(y)$.

Given $𝕊=({𝔽}_{p^n},+,\star )$ a finite semifield, the subsets

$N_l(𝕊)=\{\alpha \in 𝕊:(\alpha \star x)\star y=\alpha \star (x\star y)$ for all $x,y\in 𝕊\}$

$N_m(𝕊)=\{\alpha \in 𝕊:(x\star \alpha )\star y=x\star (\alpha \star y)$ for all $x,y\in 𝕊\}$

$N_r(𝕊)=\{\alpha \in 𝕊:(x\star y)\star \alpha =x\star (y\star \alpha )$ for all $x,y\in 𝕊\}$

are called left, middle and right nucleus of $𝕊$.

The set $N(𝕊)=N_l(𝕊)\cap N_m(𝕊)\cap N_r(𝕊)$ is called the nucleus. All these sets are finite field and, when $𝕊$ is commutative, $N_l(𝕊)=N_r(𝕊)\subseteq N_m(𝕊)$. The order of the different nuclei are invariant under isotopism.

Properties

Hence two quadratic planar functions $F,F^{\prime }$ are isotopic equivalent if their corresponding presemifields are isotopic. Moreover, we have:

• $F,F^{\prime }$ are CCZ-equivalent if and only if the corresponding presemifileds are strongly isotopic;
• for $n$ odd, isotopic coincides with strongly isotopic;
• if $F,F^{\prime }$ are isotopic equivalent, then there exists a linear map $L$ such that $F^{\prime }$ is EA-equivalent to $F(x+L(x))-F(x)-F(L(x))$;
• any commutative presemifield of odd order can generate at most two CCZ-equivalence classes of planar DO polynomials;
• if ${𝕊}_1$ and ${𝕊}_2$ are isotopic commutative semifields of characteristic $p$ with order of middle nuclei and nuclei $p^m$ and $p^k$ respectively, then either one of the following is satisfied:
  • $m/k$ is odd and the semifields are strongly isotopic,
  • $m/k$ is even and the semifields are strongly isotopic or the only isotopisms are of the form $(\alpha \star N,N,L)$ with $\alpha \in N_m({𝕊}_1)$ non-square.

Known cases of planar functions and commutative semifields

Among the known example of planar functions, the only ones that are non-quadratic are the power functions $x^{\frac{3^t+1}{2}}$ defined over ${𝔽}_{3^n}$, with $t$ is odd and gcd($t,n$)=1.

In the following the list of some known infinite families of planar functions (and corresponding commutative semifields):

• $x^2$ over ${𝔽}_{p^n}$ (finite field ${𝔽}_{p^n}$);
• $x^{p^t+1}$ over ${𝔽}_{p^n}$ with $n/gcd(t,n)$ odd (Albert's commutative twisted fields);
• $L(t^2(x))+\frac{1}{2}{x}^2$ over ${𝔽}_{p^{2km}}$ with $L(x)=\frac{1}{8}(x^{p^k}-x),t(x)=x^{p^{km}}-x$ (Dickson semifields);
• • $(ax{)}^{p^s+1}-(ax{)}^{p^k(p^s+1)}+x^{p^k+1}$
  • $b{x}^{p^s+1}+(b{x}^{p^s+1}{)}^{p^k}+c{x}^{p^k+1}$

over ${𝔽}_{p^{2k}}$ where $a,b\in {𝔽}_{2^{2k}}^{\star },b$ not square, $c\in {𝔽}_{2^{2k}}\setminus {𝔽}_{2^k},gcd(k+s,2k)=gcd(k+s,k)$ and for the first one also $gcd(p^s+1,p^k+1)\ne gcd(p^s+1,(p^k+1)/2)$. Without loss of generality it is possible to take $a=1$ and fix a value for $c$;

• $x^{p^s+1}-a^{p^t-1}{x}^{p^t+p^{2t+s}}$ over ${𝔽}_{p^{3t}},a$ primitive, $gcd(3,t)=1,t-s\equiv 0$ mod $3,3t/gcd(s,3t)$ odd;
• $x^{p^s+1}-a^{p^t-1}{x}^{p^{3t}+p^{t+s}}$ over ${𝔽}_{p^{4t}},a$ primitive, $p^s\equiv p^t\equiv 1$ mod 4, $2t/gcd(s,2t)$ odd;
• $a^{1-p}{x}^2+x^{2p^m}+a^{1-p}T(x)-T(x{)}^{p^m}$, with $T(x)=\sum _{i=0}^k(-1{)}^i{x}^{p^{2i}(p^2+1)}+a^{p-1}\sum _{j=0}^{k-1}(-1{)}^{k+j}{x}^{p^{2j+1}(p^2+1)}$, over ${𝔽}_{p^{2m}}$ for $a\in {𝔽}_{p^2}^{\star },m=2k+1$.

Cases defined for p=3

• $x^{10}\pm x^6-x^2\text{ over }{𝔽}_{p^n}\text{ with }n$ odd (Coulter-Matthews and Ding-Yuan semifields);
• $L(t^2(x))+D(t(x))+\frac{1}{2}{x}^2,\text{ over }{𝔽}_{3^{2k}}\text{ with }k\text{ odd, }t(x)=x^{3^k}-x,\beta \in {𝔽}_{3^{2k}}\setminus {𝔽}_{3^k},\alpha =t(\beta ),L(x)={\alpha }^{-5}{x}^3+x,D(x)=-{\alpha }^{-10}{x}^{10}$ (Ganley semifields);
• $L(t^2(x))+\frac{1}{2}{x}^2,\text{ over }{𝔽}_{3^{2k}}\text{ with }k\text{ odd, }t(x)=x^{3^k}-x,\beta \in {𝔽}_{3^{2k}}\setminus {𝔽}_{3^k},\alpha =t(\beta ),L(x)=-x^9-\alpha x^3+(1-{\alpha }^4)x$ (Cohen-Ganley semifileds);
• $L(t^2(x))+\frac{1}{2}{x}^2,\text{ over }{𝔽}_{3^{10}}\text{ with }t(x)=x^{243}-x,\beta \in {𝔽}_{3^{10}}\setminus {𝔽}_{3^5},\alpha =t(\beta ),L(x)=-({\alpha }^{-53}{x}^{27}+{\alpha }^{-18}{x}^9-x)$ (Penttila-Williams semifileds);
• $L(t^2(x))+D(t(x))+\frac{1}{2}{x}^2,\text{ over }{𝔽}_{3^8}\text{ with }t(x)=x^9-x,L(x)=x^{243}+x^9,D(x)=x^{246}+x^{82}-x^{10}$ (Coulter-Henderson-Kosick semifield);
• $x^2+x^{90}\text{ over }{𝔽}_{3^5}$.

Known cases of APN functions in odd characteristic

• $x^3$ over ${𝔽}_{p^n}$, $p\ne 3$;
• $x^{p^n-2}$ over ${𝔽}_{p^n}$ with $p^n\equiv 2(\mathrm{mod}3)$;
• $x^{\frac{p^n-3}{2}}$ over ${𝔽}_{p^n}$ with $p^n\equiv 3,7(\mathrm{mod}20),p^n>7,p^n\ne 27,n$ odd;
• $x^{\frac{p^n+1}{4}+\frac{p^n-1}{2}}$ over ${𝔽}_{p^n}$ with $p^n\equiv 3(\mathrm{mod}8)$;
• $x^{\frac{p^n+1}{4}}$ over ${𝔽}_{p^n}$ with $p^n\equiv 7(\mathrm{mod}8),n>1$;
• $x^{\frac{2p^n-1}{3}}$ over ${𝔽}_{p^n}$ with $p^n\equiv 2(\mathrm{mod}3)$;
• $x^{p^m+2}$ over ${𝔽}_{p^n}$ with $p^m\equiv 1(\mathrm{mod}3),n=2m$;
• $x^{3^n-3}$ over ${𝔽}_{3^n}$ with $n>1$ odd;
• $x^{\frac{3^{\frac{n+1}{2}}-1}{2}}$ over ${𝔽}_{3^n}$ with $n\equiv 3(\mathrm{mod}4),n>3$;
• $x^{\frac{3^{\frac{n+1}{2}}-1}{2}+\frac{3^n-1}{2}}$ over ${𝔽}_{3^n}$ with $n\equiv 1(\mathrm{mod}4),n>1$;
• $x^{\frac{3^{n+1}-1}{8}}$ over ${𝔽}_{3^n}$ with $n\equiv 3(\mathrm{mod}4)$;
• $x^{\frac{3^{n+1}-1}{8}+\frac{3^n-1}{4}}$ over ${𝔽}_{3^n}$ with $n\equiv 1(\mathrm{mod}4)$;
• $x^{\frac{3^{n+1}-1}{3^L+1}}$ over ${𝔽}_{3^n}$, where $L=\frac{n+1}{2^{\ell }}$ with $n\equiv -1(\mathrm{mod}{2}^{\ell })$;
• $x^{\frac{5^{\ell }+1}{2}}$ over ${𝔽}_{5^n}$ with $gcd(2n,\ell )=1$;
• $x^{\frac{5^n-1}{4}+\frac{5^{\frac{n+1}{2}}-1}{2}}$ over ${𝔽}_{5^n}$ with $n$ odd;
• $x^{\frac{5^{n+1}-1}{2(5^L+1)}+\frac{5^n-1}{4}}$ over ${𝔽}_{5^n}$, where $L=\frac{n+1}{2^{\ell }},n\equiv -1(\mathrm{mod}{2}^{\ell })$ and $\ell \ge 2$;