Commutative Presemifields and Semifields: Difference between revisions

From Boolean
Jump to navigation Jump to search
m (Undo revision 359 by Ivi062 (talk))
Tag: Undo
No edit summary
Line 33: Line 33:
Any finite presemifield can be represented by <math>\mathbb{S}=(\mathbb{F}_{p^n},+,\star)</math>,
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.
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.
Every commutative presemifield can be transformed into a commutative semifield.
Every commutative presemifield can be transformed into a commutative semifield<ref name="CouHen">Coulter R. S., Henderson M. Commutative presemifields and semifields. Advances in Math. 217, pp. 282-304, 2008</ref>.


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 <span class="definition">isotopic</span>  if there exist three linear permutations <math>T,M,N</math> of <math>\mathbb{F}_{p^n}</math> such that
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 <span class="definition">isotopic</span>  if there exist three linear permutations <math>T,M,N</math> of <math>\mathbb{F}_{p^n}</math> such that
Line 58: Line 58:
==Properties==
==Properties==
Hence two quadratic planar functions <math>F,F'</math> are isotopic equivalent if their corresponding presemifields are isotopic. Moreover, we have:
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;
* <math>F,F'</math> are CCZ-equivalent if and only if <math>\mathbb{S}_F,\mathbb{S}_{F'}</math> are strongly isotopic<ref name="BudHel">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</ref>;
* for <math>n</math> odd, isotopic coincides with 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>;
* 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>;
Line 65: Line 65:
** <math>m/k</math> is odd and the semifields are strongly isotopic,
** <math>m/k</math> is odd and the semifields are strongly isotopic,
** <math>m/k</math> is even and the semifields are strongly isotopic or the only isotopisms are of the form <math>(\alpha\star N,N,L)</math> with <math>\alpha\in N_m(\mathbb{S}_1)</math> non-square.
** <math>m/k</math> is even and the semifields are strongly isotopic or the only isotopisms are of the form <math>(\alpha\star N,N,L)</math> with <math>\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>x^{\frac{3^t+1}{2}}</math>
defined over <math>\mathbb{F}_{3^n}</math>, with <math>t</math> is odd and gcd(<math>t,n</math>)=1.
In the following the list of some known  infinite families of planar functions (and corresponding commutative semifields):
* <math>x^2</math> over <math>\mathbb{F}_{p^n}</math> (finite field <math>\mathbb{F}_{p^n}</math>);
* <math>x^{p^t+1}</math> over <math>\mathbb{F}_{p^n}</math> with <math>n/gcd(t,n)</math> odd (Albert's commutative twisted fields);
* <math>L(t^2(x))+\frac{1}{2}x^2</math> over <math>\mathbb{F}_{p^{2km}}</math> with <math>L(x)=\frac{1}{8}(x^{p^k}-x), t(x)=x^{p^{km}}-x</math> (Dickson semifields);
*
** <math>(ax)^{p^s+1}-(ax)^{p^k(p^s+1)}+x^{p^k+1}</math>
** <math>bx^{p^s+1}+(bx^{p^s+1})^{p^k}+cx^{p^k+1}</math>
over <math>\mathbb{F}_{p^{2k}}</math> where <math>a,b\in\mathbb{F}^\star_{2^{2k}}, b</math> not square, <math>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>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>a=1</math> and fix a value for <math>c</math>;
* <math>x^{p^s+1}-a^{p^t-1}x^{p^t+p^{2t+s}}</math> over <math>\mathbb{F}_{p^{3t}}, a</math> primitive, <math>gcd(3,t)=1, t-s\equiv0</math> mod <math>3, 3t/gcd(s,3t)</math> odd;
* <math>x^{p^s+1}-a^{p^t-1}x^{p^{3t}+p^{t+s}}</math> over <math>\mathbb{F}_{p^{4t}}, a</math> primitive, <math>p^s\equiv p^t\equiv1</math> mod 4, <math>2t/gcd(s,2t)</math> odd;
* <math>a^{1-p}x^2+x^{2p^m}+a^{1-p}\sum_{i=0}^k(-1)^ix^{p^{2i}(p^2+1)}+\sum_{j=0}^{k-1}(-1)^{k+j}x^{p^{2j+1}(p^2+1)}+</math>
<math>-(\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)})^{p^m}</math> over <math>\mathbb{F}_{p^{2m}}</math> for <math>a\in\mathbb{F}^star_{p^2}, m=2k+1</math>.

Revision as of 15:22, 17 September 2019

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 [math]\displaystyle{ \mathbb{S}_F,\mathbb{S}_{F'} }[/math] 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}\sum_{i=0}^k(-1)^ix^{p^{2i}(p^2+1)}+\sum_{j=0}^{k-1}(-1)^{k+j}x^{p^{2j+1}(p^2+1)}+ }[/math]
[math]\displaystyle{ -(\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)})^{p^m} }[/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