Commutative Presemifields and Semifields: Difference between revisions

From Boolean
Jump to navigation Jump to search
mNo edit summary
 
(13 intermediate revisions by 2 users not shown)
Line 1: Line 1:
=Introduction=
=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
* <span class="definition">linear</span> if <math>F(x)=\sum_{j=0}^{n-1}a_jx^{p^j} </math>,
* <span class="definition">affine</span> if it is the sum of a linear function and a constant,
* <span class="definition">DO</span> (Dembowski-Ostrim) polynomial if <math>F(x)=\sum_{0\le i\le j<n}a_{ij}x^{p^i+p^j} </math>,
* <span class="definition">quadratic</span> 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 <span class="definition">differentially <math>\delta</math>-uniform</span> 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 ([[differential uniformity|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:
*<span class="definition">affine equivalent</span> if <math>F'=A_1\circ F\circ A_2</math>, where <math>A_1,A_2</math> are affine permutations;
*<span class="definition">EA-equivalent</span> (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>;
*<span class="definition">CCZ-equivalent</span> 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 <span class="definition">isotopic equivalence</span> is more general than CCZ-equivalence, where two maps are isotopic equivalent if the corresponding presemifields are isotopic.
 
=On Presemifields and Semifields=
A <span class="definition">presemifield</span> is a ring with left and right distributivity and with no zero divisor.
A <span class="definition">presemifield</span> is a ring with left and right distributivity and with no zero divisor.
A presemifield with a multiplicative identity is called a <span class="definition">semifield</span>.
A presemifield with a multiplicative identity is called a <span class="definition">semifield</span>.
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<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 permutation <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
<math>T(x\star y)=M(x)\circ N(y)</math>,
<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 <span class="definition">strongly isotopic</span>.
for any <math>x,y\in\mathbb{F}_{p^n}</math>. If <math>M=N</math> then they are called <span class="definition">strongly isotopic</span>.
Each commutative presemifields of odd order defines a [[Planar Functions|planar]] DO polynomial and viceversa:
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_\mathcal{S}(x)=\frac{1}{2}(x\star x)</math>;
* 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>.
* 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:
Given <math>\mathbb{S}=(\mathbb{F}_{p^n},+,\star)</math> a finite semifield, the subsets
* <math>F,F'</math> are CCZ-equivalent if and only if <math>\mathbb{S}_F,\mathbb{S}_{F'}</math> are strongly isotopic;
 
<math>N_l(\mathbb{S})=\{\alpha\in\mathbb{S} : (\alpha\star x)\star y=\alpha\star(x\star y)</math> for all <math>x,y\in\mathbb{S}\}</math>
 
<math>N_m(\mathbb{S})=\{\alpha\in\mathbb{S} : (x\star\alpha)\star y=x\star(\alpha\star y)</math> for all <math>x,y\in\mathbb{S}\}</math>
 
<math>N_r(\mathbb{S})=\{\alpha\in\mathbb{S} : (x\star y)\star \alpha=x\star(y\star \alpha)</math> for all <math>x,y\in\mathbb{S}\}</math>
 
are called left, middle and right nucleus of <math>\mathbb{S}</math>.
 
The set <math>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>\mathbb{S}</math> is commutative,  <math>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>F,F'</math> are <b>isotopic equivalent</b> if their corresponding presemifields are isotopic. Moreover, we have:
* <math>F,F'</math> are CCZ-equivalent if and only if the corresponding presemifileds 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>;
* any commutative presemifield of odd order can generate at most two CCZ-equivalence classes of planar DO polynomials;
* if <math>\mathbb{S}_1</math> and <math>\mathbb{S}_2</math> are isotopic commutative semifields of characteristic <math>p</math> with order of middle nuclei and nuclei <math>p^m</math> and <math>p^k</math> respectively, then either one of the following is satisfied:
** <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.
 
=Known cases of 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}T(x)-T(x)^{p^m}</math>, with <math>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>\mathbb{F}_{p^{2m}}</math> for <math>a\in\mathbb{F}^\star_{p^2}, m=2k+1</math>.
 
==Cases defined for <i>p</i>=3==
* <math>x^{10}\pm x^6-x^2 \mbox{ over } \mathbb{F}_{p^n} \mbox{ with } n</math> odd (Coulter-Matthews and Ding-Yuan semifields);
* <math>L(t^2(x))+D(t(x))+\frac{1}{2}x^2, \mbox{ over } \mathbb{F}_{3^{2k}} \mbox{ with } k \mbox{ odd, } t(x)=x^{3^k}-x, \beta\in\mathbb{F}_{3^{2k}}\setminus\mathbb{F}_{3^k}, \alpha=t(\beta), L(x)=\alpha^{-5}x^3+x, D(x)=-\alpha^{-10}x^{10}</math> (Ganley semifields);
* <math>L(t^2(x))+\frac{1}{2}x^2, \mbox{ over } \mathbb{F}_{3^{2k}} \mbox{ with } k \mbox{ odd, } t(x)=x^{3^k}-x, \beta\in\mathbb{F}_{3^{2k}}\setminus\mathbb{F}_{3^k}, \alpha=t(\beta), L(x)=-x^9-\alpha x^3+(1-\alpha^4)x</math> (Cohen-Ganley semifileds);
* <math>L(t^2(x))+\frac{1}{2}x^2, \mbox{ over } \mathbb{F}_{3^{10}} \mbox{ with } t(x)=x^{243}-x, \beta\in\mathbb{F}_{3^{10}}\setminus\mathbb{F}_{3^5}, \alpha=t(\beta), L(x)=-(\alpha^{-53}x^{27}+\alpha^{-18}x^9-x)</math> (Penttila-Williams semifileds);
* <math>L(t^2(x))+D(t(x))+\frac{1}{2}x^2, \mbox{ over } \mathbb{F}_{3^{8}} \mbox{ with } t(x)=x^9-x, L(x)=x^{243}+x^9, D(x)=x^{246}+x^{82}-x^{10}</math> (Coulter-Henderson-Kosick semifield);
* <math>x^2+x^{90} \mbox{ over } \mathbb{F}_{3^5}</math>.
 
 
=Known cases of APN functions in odd characteristic=
*<math>x^3</math> over <math>\mathbb{F}_{p^n}</math>, <math> p \neq 3 </math>;
*<math>x^{p^n-2}</math> over <math>\mathbb{F}_{p^n}</math> with <math> p^n \equiv 2 \pmod 3 </math>;
*<math>x^{\frac{p^n-3}{2}}</math> over <math>\mathbb{F}_{p^n}</math> with <math> p^n \equiv 3,7 \pmod {20},~ p^n>7,~ p^n \neq 27, n </math> odd;
*<math>x^{\frac{p^n+1}{4}+\frac{p^n-1}{2}}</math> over <math>\mathbb{F}_{p^n}</math> with <math> p^n \equiv 3 \pmod 8 </math>;
*<math>x^{\frac{p^n+1}{4}}</math> over <math>\mathbb{F}_{p^n}</math> with <math> p^n \equiv 7 \pmod 8,~ n>1 </math>;
*<math>x^{\frac{2p^n-1}{3}}</math> over <math>\mathbb{F}_{p^n}</math> with <math> p^n \equiv 2 \pmod 3 </math>;
*<math>x^{p^m+2}</math> over <math>\mathbb{F}_{p^n}</math> with <math> p^m \equiv 1 \pmod 3,~ n=2m </math>;
*<math>x^{3^n-3}</math> over <math>\mathbb{F}_{3^n}</math> with <math> n>1</math> odd;
*<math>x^{\frac{3^\frac{n+1}{2}-1}{2}}</math> over <math>\mathbb{F}_{3^n}</math> with <math> n \equiv 3 \pmod 4,~ n>3</math>;
*<math>x^{\frac{3^\frac{n+1}{2}-1}{2}+\frac{3^n-1}{2}}</math> over <math>\mathbb{F}_{3^n}</math> with <math> n \equiv 1 \pmod 4,~ n>1</math>;
*<math>x^{\frac{3^{n+1}-1}{8}}</math> over <math>\mathbb{F}_{3^n}</math> with <math> n \equiv 3 \pmod 4 </math>;
*<math>x^{\frac{3^{n+1}-1}{8}+\frac{3^{n}-1}{4}}</math> over <math>\mathbb{F}_{3^n}</math> with <math> n \equiv 1 \pmod 4 </math>;
*<math>x^{\frac{3^{n+1}-1}{3^L+1}}</math> over <math>\mathbb{F}_{3^n}</math>, where <math> L={\frac{n+1}{2^{\ell}}} </math> with <math> n \equiv -1 \pmod {2^\ell} </math>;
*<math>x^{\frac{5^\ell+1}{2}}</math> over <math>\mathbb{F}_{5^n}</math> with <math> \gcd(2n, \ell)=1 </math>;
*<math>x^{\frac{5^n-1}{4}+ \frac{5^{\frac{n+1}{2}}-1}{2}}</math> over <math>\mathbb{F}_{5^n}</math> with <math> n </math> odd;
*<math>x^{\frac{5^{n+1}-1}{2(5^L+1)}+ \frac{5^n-1}{4}}</math> over <math>\mathbb{F}_{5^n}</math>, where <math> L={\frac{n+1}{2^{\ell}}},~n \equiv -1 \pmod {2^\ell} </math> and <math> \ell \geq 2 </math>;

Latest revision as of 12:20, 6 March 2023

Background

For a prime 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} and a positive integer 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 n} let 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^n}} be the finite field 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 p^n} elements. Let 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 F} be a map from the finite field to itself. Such function admits a unique representation as a polynomial of degree at most , i.e.

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 F(x)=\sum_{j=0}^{p^n-1}a_jx^j, a_j\in\mathbb{F}_{p^n}} .

The function 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 F} is

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

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

A function 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 F} is called planar or perfect nonlinear (PN) if 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 \delta_F=1} . Obviously such functions exist only for an odd prime. In the even case the smallest possible case 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 \delta} is two (APN function).

For planar function we have that the all the nonzero derivatives, 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 D_aF(x)=F(x+a)-F(x)} , are permutations.

Equivalence Relations

Two functions 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 F} and 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 F'} from 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^n}} to itself are called:

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

Two presemifields 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{S}_1=(\mathbb{F}_{p^n},+,\star)} and 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{S}_2=(\mathbb{F}_{p^n},+,\circ)} are called isotopic if there exist three linear permutations 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,M,N} of 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^n}} such that 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\star y)=M(x)\circ N(y)} , for any 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,y\in\mathbb{F}_{p^n}} . If 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 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 (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{S}=(\mathbb{F}_{p^n},+,\star)} let 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 F_\mathbb{S}(x)=\frac{1}{2}(x\star x)} ;
  • given 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 F} let defined by .

Given a finite semifield, the subsets

for all

for all

for all

are called left, middle and right nucleus of .

The set is called the nucleus. All these sets are finite field and, when 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{S}} is commutative, 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 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 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 F,F'} are isotopic equivalent if their corresponding presemifields are isotopic. Moreover, we have:

  • 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 F,F'} are CCZ-equivalent if and only if the corresponding presemifileds are strongly isotopic[2];
  • 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 n} odd, isotopic coincides with strongly isotopic;
  • if 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 F,F'} are isotopic equivalent, then there exists a linear map 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 L} such that 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 F'} is EA-equivalent to 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 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 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{S}_1} and 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{S}_2} are isotopic commutative semifields of characteristic 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} with order of middle nuclei and nuclei 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^m} and 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^k} respectively, then either one of the following is satisfied:
    • 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 m/k} is odd and the semifields are strongly isotopic,
    • 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 m/k} is even and the semifields are strongly isotopic or the only isotopisms are of the form 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 (\alpha\star N,N,L)} 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 \alpha\in N_m(\mathbb{S}_1)} non-square.

Known cases of 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 (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^{\frac{3^t+1}{2}}} defined over , 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} is odd and gcd(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,n} )=1.

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

  • 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^2} 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^n}} (finite field 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^n}} );
  • 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^t+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^n}} 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 n/gcd(t,n)} odd (Albert's commutative twisted fields);
  • 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 L(t^2(x))+\frac{1}{2}x^2} 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^{2km}}} 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 L(x)=\frac{1}{8}(x^{p^k}-x), t(x)=x^{p^{km}}-x} (Dickson semifields);
    • 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 (ax)^{p^s+1}-(ax)^{p^k(p^s+1)}+x^{p^k+1}}

over where not square, and for the first one also . Without loss of generality it is possible to take and fix a value 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 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 odd;
  • over primitive, mod 4, odd;
  • , with , over for .

Cases defined for p=3

  • odd (Coulter-Matthews and Ding-Yuan semifields);
  • (Ganley semifields);
  • (Cohen-Ganley semifileds);
  • (Penttila-Williams semifileds);
  • (Coulter-Henderson-Kosick semifield);
  • .


Known cases of APN functions in odd characteristic

  • 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^3} 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^n}} , 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 \neq 3 } ;
  • 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^n-2}} 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^n}} 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 x^{\frac{p^n-3}{2}}} 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^n}} 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 p^n \equiv 3,7 \pmod {20},~ p^n>7,~ p^n \neq 27, n } 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^{\frac{p^n+1}{4}+\frac{p^n-1}{2}}} over 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 p^n \equiv 3 \pmod 8 } ;
  • 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^{\frac{p^n+1}{4}}} 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^n}} 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 p^n \equiv 7 \pmod 8,~ n>1 } ;
  • 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^{\frac{2p^n-1}{3}}} over 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 p^n \equiv 2 \pmod 3 } ;
  • 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^m+2}} over with ;
  • 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}_{3^n}} 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 n>1} 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^{\frac{3^\frac{n+1}{2}-1}{2}}} 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}_{3^n}} 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 x^{\frac{3^\frac{n+1}{2}-1}{2}+\frac{3^n-1}{2}}} 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}_{3^n}} 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 n \equiv 1 \pmod 4,~ n>1} ;
  • over with ;
  • over 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 x^{\frac{3^{n+1}-1}{3^L+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}_{3^n}} , where 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 L={\frac{n+1}{2^{\ell}}} } 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 n \equiv -1 \pmod {2^\ell} } ;
  • 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^{\frac{5^\ell+1}{2}}} over 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 \gcd(2n, \ell)=1 } ;
  • over with 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^{\frac{5^{n+1}-1}{2(5^L+1)}+ \frac{5^n-1}{4}}} 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}_{5^n}} , where 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 L={\frac{n+1}{2^{\ell}}},~n \equiv -1 \pmod {2^\ell} } and 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 \ell \geq 2 } ;
  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
Retrieved from "http://boolean.wiki.uib.no/index.php?title=Commutative_Presemifields_and_Semifields&oldid=605"