Commutative Presemifields and Semifields

From Boolean
Revision as of 14:15, 29 August 2019 by Ivi062 (talk | contribs)
Jump to navigation Jump to search

Background

For a prime [math]\displaystyle{ p }[/math] and a positive integer [math]\displaystyle{ n }[/math] let [math]\displaystyle{ \mathbb{F}_{p^n} }[/math] be the finite field with [math]\displaystyle{ p^n }[/math] elements. Let [math]\displaystyle{ 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]\displaystyle{ p^n-1 }[/math], i.e.

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

The function [math]\displaystyle{ F }[/math] is

  • linear if [math]\displaystyle{ 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]\displaystyle{ F(x)=\sum_{0\le i\le j\lt 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]\displaystyle{ \delta }[/math] a positive integer, the function [math]\displaystyle{ F }[/math] is called differentially [math]\displaystyle{ \delta }[/math]-uniform if for any pairs [math]\displaystyle{ a,b\in\mathbb{F}_{p^n} }[/math], with [math]\displaystyle{ a\ne0 }[/math], the equation [math]\displaystyle{ F(x+a)-F(x)=b }[/math] admits at most [math]\displaystyle{ \delta }[/math] solutions.

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

For planar function we have that the all the nonzero derivatives, [math]\displaystyle{ D_aF(x)=F(x+a)-F(x) }[/math], are permutations.

Equivalence Relations

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

  • affine equivalent if [math]\displaystyle{ F'=A_1\circ F\circ A_2 }[/math], where [math]\displaystyle{ A_1,A_2 }[/math] are affine permutations;
  • EA-equivalent (extended-affine) if [math]\displaystyle{ F'=F''+A }[/math], where [math]\displaystyle{ A }[/math] is affine and [math]\displaystyle{ F'' }[/math] is afffine equivalent to [math]\displaystyle{ F }[/math];
  • CCZ-equivalent if there exists an affine permutation [math]\displaystyle{ \mathcal{L} }[/math] of [math]\displaystyle{ \mathbb{F}_{p^n}\times\mathbb{F}_{p^n} }[/math] such that [math]\displaystyle{ \mathcal{L}(G_F)=G_{F'} }[/math], where [math]\displaystyle{ 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]\displaystyle{ \mathbb{S}=(\mathbb{F}_{p^n},+,\star) }[/math], for [math]\displaystyle{ p }[/math] a prime, [math]\displaystyle{ n }[/math] a positive integer, [math]\displaystyle{ \mathbb{S}=(\mathbb{F}_{p^n},+) }[/math] additive group and [math]\displaystyle{ x\star y }[/math] multiplication linear in each variable.

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

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

Given [math]\displaystyle{ \mathbb{S}=(\mathbb{F}_{p^n},+,\star) }[/math] a finite semifield, the subsets

[math]\displaystyle{ N_l(\mathbb{S})=\{\alpha\in\mathbb{S} : (\alpha\star x)\star y=\alpha\star(x\star y) }[/math] for all [math]\displaystyle{ x,y\in\mathbb{S}\} }[/math]

[math]\displaystyle{ N_m(\mathbb{S})=\{\alpha\in\mathbb{S} : (x\star\alpha)\star y=x\star(\alpha\star y) }[/math] for all [math]\displaystyle{ x,y\in\mathbb{S}\} }[/math]

[math]\displaystyle{ N_r(\mathbb{S})=\{\alpha\in\mathbb{S} : (x\star y)\star \alpha=x\star(y\star \alpha) }[/math] for all [math]\displaystyle{ x,y\in\mathbb{S}\} }[/math]

are called left, middle and right nucleus of [math]\displaystyle{ \mathbb{S} }[/math].

Properties

Hence two quadratic planar functions [math]\displaystyle{ F,F' }[/math] are isotopic equivalent if their corresponding presemifields are isotopic. Moreover, we have:

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