Difference between revisions of "APN Permutations"

From Boolean Functions
Jump to: navigation, search
m
m
 
Line 3: Line 3:
 
== Component Functions ==
 
== Component Functions ==
  
βˆ’
An <math>(n,n)</math>-function <math>F</math> is a permutation if and only if all of its components <math>F_\lambda</math> for <math>\lambda \in \mathbb{F}_{2^n}^*</math> are balanced.
+
An (𝑛,𝑛)-function 𝐹 is a permutation if and only if all of its components 𝐹<sub>Ξ»</sub> for Ξ» ∈ 𝔽*<sub>2<sup>𝑛</sup></sub> are balanced.
  
 
== Autocorrelation Functions of the Directional Derivatives ==
 
== Autocorrelation Functions of the Directional Derivatives ==
Line 11: Line 11:
 
<div><math>\sum_{a \in \mathbb{F}_{2^n}^*} \mathcal{F}(D_af_\lambda) = -2^n</math></div>
 
<div><math>\sum_{a \in \mathbb{F}_{2^n}^*} \mathcal{F}(D_af_\lambda) = -2^n</math></div>
  
βˆ’
for any <math>\lambda \in \mathbb{F}_{2^n}^*</math>.
+
for any Ξ» ∈ 𝔽*<sub>2<sup>𝑛</sup></sub>.
  
βˆ’
Equivalently <ref name="bercanchalai2006"> Thierry Berger, Anne Canteaut, Pascale Charpin, Yann Laigle-Chapuy, ''On Almost Perfect Nonlinear Functions Over GF(2^n)'', IEEE Transactions on Information Theory, 2006 Sep,52(9),4160-70</ref>, <math>F</math> is a permutation if and only if
+
Equivalently <ref name="bercanchalai2006"> Thierry Berger, Anne Canteaut, Pascale Charpin, Yann Laigle-Chapuy, ''On Almost Perfect Nonlinear Functions Over GF(2^n)'', IEEE Transactions on Information Theory, 2006 Sep,52(9),4160-70</ref>, 𝐹 is a permutation if and only if
  
 
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}(D_af_\lambda) = -2^n</math></div>
 
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}(D_af_\lambda) = -2^n</math></div>
  
βˆ’
for any <math>\lambda \in \mathbb{F}_{2^n}^*</math>.
+
for any Ξ» ∈ 𝔽*<sub>2<sup>𝑛</sup></sub>.
  
 
= Characterization of APN Permutations =
 
= Characterization of APN Permutations =
Line 23: Line 23:
 
Clearly we have that no component function can be of degree 1. (This result is true for general APN maps)
 
Clearly we have that no component function can be of degree 1. (This result is true for general APN maps)
  
βˆ’
For <i>n</i> even we have also that no component can be partially-bent<ref name="CalSalVil"> Marco Calderini, Massimiliano Sala, Irene Villa, ''A note on APN permutations in even dimension'', Finite Fields and Their Applications, vol. 46, 1-16, 2017</ref>.
+
For 𝑛 even we have also that no component can be partially-bent<ref name="CalSalVil"> Marco Calderini, Massimiliano Sala, Irene Villa, ''A note on APN permutations in even dimension'', Finite Fields and Their Applications, vol. 46, 1-16, 2017</ref>.
 
This implies that, in even dimension, no component can be of degree 2.
 
This implies that, in even dimension, no component can be of degree 2.
  
 
== Autocorrelation Functions of the Directional Derivatives ==
 
== Autocorrelation Functions of the Directional Derivatives ==
  
βˆ’
An <math>(n,n)</math>-function <math>F</math> is an APN permutation if and only if <ref name="bercanchalai2006"></ref>
+
An (𝑛,𝑛)-function 𝐹 is an APN permutation if and only if <ref name="bercanchalai2006"></ref>
  
 
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}(D_af_\lambda) = -2^n</math></div>
 
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}(D_af_\lambda) = -2^n</math></div>
 
and
 
and
 
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}^2(D_af_\lambda) = 2^{2n}</math></div>
 
<div><math>\sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}^2(D_af_\lambda) = 2^{2n}</math></div>
βˆ’
for any <math>a \in \mathbb{F}_{2^n}^*</math>.
+
for any π‘Ž ∈ 𝔽*<sub>2<sup>𝑛</sup></sub>.

Latest revision as of 14:05, 11 October 2019

Characterization of Permutations

Component Functions

An (𝑛,𝑛)-function 𝐹 is a permutation if and only if all of its components 𝐹λ for Ξ» ∈ 𝔽*2𝑛 are balanced.

Autocorrelation Functions of the Directional Derivatives

The characterization in terms of the component functions given above can be equivalently expressed as

for any Ξ» ∈ 𝔽*2𝑛.

Equivalently [1], 𝐹 is a permutation if and only if

for any Ξ» ∈ 𝔽*2𝑛.

Characterization of APN Permutations

On the component functions

Clearly we have that no component function can be of degree 1. (This result is true for general APN maps)

For 𝑛 even we have also that no component can be partially-bent[2]. This implies that, in even dimension, no component can be of degree 2.

Autocorrelation Functions of the Directional Derivatives

An (𝑛,𝑛)-function 𝐹 is an APN permutation if and only if [1]

and

for any π‘Ž ∈ 𝔽*2𝑛.

  1. ↑ 1.0 1.1 Thierry Berger, Anne Canteaut, Pascale Charpin, Yann Laigle-Chapuy, On Almost Perfect Nonlinear Functions Over GF(2^n), IEEE Transactions on Information Theory, 2006 Sep,52(9),4160-70
  2. ↑ Marco Calderini, Massimiliano Sala, Irene Villa, A note on APN permutations in even dimension, Finite Fields and Their Applications, vol. 46, 1-16, 2017