Commutative Presemifields and Semifields

From Boolean
Revision as of 08:50, 23 September 2019 by Ivi062 (talk | contribs) (→‎Properties)
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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. Every commutative presemifield can be transformed into a commutative semifield[1].

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].

The set [math]\displaystyle{ N(\mathbb{S})=N_l(\mathbb{S})\cap N_m(\mathbb{S})\cap N_r(\mathbb{S}) }[/math] is called the nucleus. All these sets are finite field and, when [math]\displaystyle{ \mathbb{S} }[/math] is commutative, [math]\displaystyle{ N_l(\mathbb{S})=N_r(\mathbb{S})\subseteq N_m(\mathbb{S}) }[/math]. The order of the different nuclei are invariant under isotopism.

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 the corresponding presemifileds are strongly isotopic[2];
  • 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];
  • any commutative presemifield of odd order can generate at most two CCZ-equivalence classes of planar DO polynomials;
  • if [math]\displaystyle{ \mathbb{S}_1 }[/math] and [math]\displaystyle{ \mathbb{S}_2 }[/math] are isotopic commutative semifields of characteristic [math]\displaystyle{ p }[/math] with order of middle nuclei and nuclei [math]\displaystyle{ p^m }[/math] and [math]\displaystyle{ p^k }[/math] respectively, then either one of the following is satisfied:
    • [math]\displaystyle{ m/k }[/math] is odd and the semifields are strongly isotopic,
    • [math]\displaystyle{ m/k }[/math] is even and the semifields are strongly isotopic or the only isotopisms are of the form [math]\displaystyle{ (\alpha\star N,N,L) }[/math] with [math]\displaystyle{ \alpha\in N_m(\mathbb{S}_1) }[/math] 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 [math]\displaystyle{ x^{\frac{3^t+1}{2}} }[/math] defined over [math]\displaystyle{ \mathbb{F}_{3^n} }[/math], with [math]\displaystyle{ t }[/math] is odd and gcd([math]\displaystyle{ t,n }[/math])=1.

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

  • [math]\displaystyle{ x^2 }[/math] over [math]\displaystyle{ \mathbb{F}_{p^n} }[/math] (finite field [math]\displaystyle{ \mathbb{F}_{p^n} }[/math]);
  • [math]\displaystyle{ x^{p^t+1} }[/math] over [math]\displaystyle{ \mathbb{F}_{p^n} }[/math] with [math]\displaystyle{ n/gcd(t,n) }[/math] odd (Albert's commutative twisted fields);
  • [math]\displaystyle{ L(t^2(x))+\frac{1}{2}x^2 }[/math] over [math]\displaystyle{ \mathbb{F}_{p^{2km}} }[/math] with [math]\displaystyle{ L(x)=\frac{1}{8}(x^{p^k}-x), t(x)=x^{p^{km}}-x }[/math] (Dickson semifields);
    • [math]\displaystyle{ (ax)^{p^s+1}-(ax)^{p^k(p^s+1)}+x^{p^k+1} }[/math]
    • [math]\displaystyle{ bx^{p^s+1}+(bx^{p^s+1})^{p^k}+cx^{p^k+1} }[/math]

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

  • [math]\displaystyle{ x^{p^s+1}-a^{p^t-1}x^{p^t+p^{2t+s}} }[/math] over [math]\displaystyle{ \mathbb{F}_{p^{3t}}, a }[/math] primitive, [math]\displaystyle{ gcd(3,t)=1, t-s\equiv0 }[/math] mod [math]\displaystyle{ 3, 3t/gcd(s,3t) }[/math] odd;
  • [math]\displaystyle{ x^{p^s+1}-a^{p^t-1}x^{p^{3t}+p^{t+s}} }[/math] over [math]\displaystyle{ \mathbb{F}_{p^{4t}}, a }[/math] primitive, [math]\displaystyle{ p^s\equiv p^t\equiv1 }[/math] mod 4, [math]\displaystyle{ 2t/gcd(s,2t) }[/math] odd;
  • [math]\displaystyle{ a^{1-p}x^2+x^{2p^m}+a^{1-p}T(x)-T(x)^{p^m} }[/math], with [math]\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)} }[/math], over [math]\displaystyle{ \mathbb{F}_{p^{2m}} }[/math] for [math]\displaystyle{ a\in\mathbb{F}^\star_{p^2}, m=2k+1 }[/math].
  1. Coulter R. S., Henderson M. Commutative presemifields and semifields. Advances in Math. 217, pp. 282-304, 2008
  2. Budaghyan L., Helleseth T. On Isotopism of Commutative Presemifields and CCZ-Equivalence of Functions. Special Issue on Cryptography of International Journal of Foundations of Computer Science, v. 22/6), pp- 1243-1258, 2011