Commutative Presemifields and Semifields

Background

For a prime Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p} and a positive integer $n$ let $\mathbb {F} _{p^{n}}$ be the finite field with Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p^{n}-1} , i.e.

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F(x)=\sum _{j=0}^{p^{n}-1}a_{j}x^{j},a_{j}\in \mathbb {F} _{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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F(x)=\sum _{0\leq i\leq 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a,b\in \mathbb {F} _{p^{n}}} , with $a\neq 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \delta _{F}=1} . Obviously such functions exist only for Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F'} from $\mathbb {F} _{p^{n}}$ to itself are called:

• affine equivalent if Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F'=A_{1}\circ F\circ A_{2}} , where $A_{1},A_{2}$ are affine permutations;
• EA-equivalent (extended-affine) if Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F'=F''+A} , where $A$ is affine and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F''} is afffine equivalent to $F$;
• CCZ-equivalent if there exists an affine permutation ${\mathcal {L}}$ of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {F} _{p^{n}}\times \mathbb {F} _{p^{n}}} such that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathcal {L}}(G_{F})=G_{F'}} , where Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G_{F}=\lbrace (x,F(x)):x\in \mathbb {F} _{p^{n}}\rbrace } .

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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {S} =(\mathbb {F} _{p^{n}},+,\star )} , for Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p} a prime, $n$ a positive integer, $\mathbb {S} =(\mathbb {F} _{p^{n}},+)$ additive group and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x\star y} multiplication linear in each variable. Every commutative presemifield can be transformed into a commutative semifield.

Two presemifields $\mathbb {S} _{1}=(\mathbb {F} _{p^{n}},+,\star )$ and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {S} _{2}=(\mathbb {F} _{p^{n}},+,\circ )} are called isotopic if there exist three linear permutations Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle T,M,N} of $\mathbb {F} _{p^{n}}$ such that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle T(x\star y)=M(x)\circ N(y)} , for any Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x,y\in \mathbb {F} _{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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {S} =(\mathbb {F} _{p^{n}},+,\star )} let $F_{\mathbb {S} }(x)={\frac {1}{2}}(x\star x)$;
• given $F$ let Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {S} _{F}=(\mathbb {F} _{p^{n}},+,\star )} defined by Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x\star y=F(x+y)-F(x)-F(y)} .

Given Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {S} =(\mathbb {F} _{p^{n}},+,\star )} a finite semifield, the subsets

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle N_{l}(\mathbb {S} )=\{\alpha \in \mathbb {S} :(\alpha \star x)\star y=\alpha \star (x\star y)} for all $x,y\in \mathbb {S} \}$

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle N_{m}(\mathbb {S} )=\{\alpha \in \mathbb {S} :(x\star \alpha )\star y=x\star (\alpha \star y)} for all $x,y\in \mathbb {S} \}$

$N_{r}(\mathbb {S} )=\{\alpha \in \mathbb {S} :(x\star y)\star \alpha =x\star (y\star \alpha )$ for all $x,y\in \mathbb {S} \}$

are called left, middle and right nucleus of $\mathbb {S}$.

The set $N(\mathbb {S} )=N_{l}(\mathbb {S} )\cap N_{m}(\mathbb {S} )\cap N_{r}(\mathbb {S} )$ is called the nucleus. All these sets are finite field and, when $\mathbb {S}$ is commutative, Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle N_{l}(\mathbb {S} )=N_{r}(\mathbb {S} )\subseteq N_{m}(\mathbb {S} )} . The order of the different nuclei are invariant under isotopism.

Properties

Hence two quadratic planar functions $F,F'$ are isotopic equivalent if their corresponding presemifields are isotopic. Moreover, we have:

• $F,F'$ are CCZ-equivalent if and only if the corresponding presemifileds are strongly isotopic;
• for $n$ odd, isotopic coincides with strongly isotopic;
• if $F,F'$ are isotopic equivalent, then there exists a linear map Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle L} such that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F'} is EA-equivalent to Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 $\mathbb {S} _{1}$ and $\mathbb {S} _{2}$ are isotopic commutative semifields of characteristic Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p} with order of middle nuclei and nuclei Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p^{m}} and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p^{k}} respectively, then either one of the following is satisfied:
  • Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle m/k} is odd and the semifields are strongly isotopic,
  • Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle m/k} is even and the semifields are strongly isotopic or the only isotopisms are of the form Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (\alpha \star N,N,L)} with $\alpha \in N_{m}(\mathbb {S} _{1})$ non-square.

Known cases od planar functions and commutative semifields

Among the known example of planar functions, the only ones that are non-quadratic are the power functions Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x^{\frac {3^{t}+1}{2}}} defined over Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {F} _{3^{n}}} , with $t$ is odd and gcd(Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle t,n} )=1.

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

• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x^{2}} over $\mathbb {F} _{p^{n}}$ (finite field $\mathbb {F} _{p^{n}}$);
• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x^{p^{t}+1}} over $\mathbb {F} _{p^{n}}$ with Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n/gcd(t,n)} odd (Albert's commutative twisted fields);
• $L(t^{2}(x))+{\frac {1}{2}}x^{2}$ over Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {F} _{p^{2km}}} with Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle L(x)={\frac {1}{8}}(x^{p^{k}}-x),t(x)=x^{p^{km}}-x} (Dickson semifields);
• • Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (ax)^{p^{s}+1}-(ax)^{p^{k}(p^{s}+1)}+x^{p^{k}+1}}
  • Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle bx^{p^{s}+1}+(bx^{p^{s}+1})^{p^{k}}+cx^{p^{k}+1}}

over $\mathbb {F} _{p^{2k}}$ where Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a,b\in \mathbb {F} _{2^{2k}}^{\star },b} not square, Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle c\in \mathbb {F} _{2^{2k}}\setminus \mathbb {F} _{2^{k}},gcd(k+s,2k)=gcd(k+s,k)} and for the first one also Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle gcd(p^{s}+1,p^{k}+1)\neq gcd(p^{s}+1,(p^{k}+1)/2)} . Without loss of generality it is possible to take Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a=1} and fix a value for $c$;

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{p^s+1}-a^{p^t-1}x^{p^t+p^{2t+s}}} over Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{p^{3t}}, a} primitive, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle gcd(3,t)=1, t-s\equiv0} mod Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3, 3t/gcd(s,3t)} odd;
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{p^s+1}-a^{p^t-1}x^{p^{3t}+p^{t+s}}} over Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{p^{4t}}, a} primitive, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p^s\equiv p^t\equiv1} mod 4, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2t/gcd(s,2t)} odd;
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{1-p}x^2+x^{2p^m}+a^{1-p}T(x)-T(x)^{p^m}} , with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(x)=\sum_{i=0}^k(-1)^ix^{p^{2i}(p^2+1)}+a^{p-1}\sum_{j=0}^{k-1}(-1)^{k+j}x^{p^{2j+1}(p^2+1)}} , over Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{p^{2m}}} for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\in\mathbb{F}^\star_{p^2}, m=2k+1} .