Commutative Presemifields and Semifields

Background

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

<math>F(x)=\sum_{j=0}^{p^n-1}a_jx^j, a_j\in\mathbb{F}_{p^n}</math>.

The function <math>F</math> is

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

For <math>\delta</math> a positive integer, the function <math>F</math> is called differentially <math>\delta</math>-uniform if for any pairs <math>a,b\in\mathbb{F}_{p^n}</math>, with <math>a\ne0</math>, the equation <math>F(x+a)-F(x)=b</math> admits at most <math>\delta</math> solutions.

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

For planar function we have that the all the nonzero derivatives, <math>D_aF(x)=F(x+a)-F(x)</math>, are permutations.

Equivalence Relations

Two functions <math>F</math> and <math>F'</math> from <math>\mathbb{F}_{p^n}</math> to itself are called:

• affine equivalent if <math>F'=A_1\circ F\circ A_2</math>, where <math>A_1,A_2</math> are affine permutations;
• EA-equivalent (extended-affine) if <math>F'=F+A</math>, where <math>A</math> is affine and <math>F</math> is afffine equivalent to <math>F</math>;
• CCZ-equivalent if there exists an affine permutation <math>\mathcal{L}</math> of <math>\mathbb{F}_{p^n}\times\mathbb{F}_{p^n}</math> such that <math>\mathcal{L}(G_F)=G_{F'}</math>, where <math>G_F=\lbrace (x,F(x)) : x\in\mathbb{F}_{p^n}\rbrace</math>.

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 <math>\mathbb{S}=(\mathbb{F}_{p^n},+,\star)</math>, for <math>p</math> a prime, <math>n</math> a positive integer, <math>\mathbb{S}=(\mathbb{F}_{p^n},+)</math> additive group and <math>x\star y</math> multiplication linear in each variable.

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

• given <math>\mathbb{S}=(\mathbb{F}_{p^n},+,\star)</math> let <math>F_\mathbb{S}(x)=\frac{1}{2}(x\star x)</math>;
• given <math>F</math> let <math>\mathbb{S}_F=(\mathbb{F}_{p^n},+,\star)</math> defined by <math>x\star y=F(x+y)-F(x)-F(y)</math>.

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

• <math>F,F'</math> are CCZ-equivalent if and only if <math>\mathbb{S}_F,\mathbb{S}_{F'}</math> are strongly isotopic;
• for <math>n</math> odd, isotopic coincides with strongly isotopic;
• if <math>F,F'</math> are isotopic equivalent, then there exists a linear map <math>L</math> such that <math>F'</math> is EA-equivalent to <math>F(x+L(x))-F(x)-F(L(x))</math>.