Difference between revisions of "APN Permutations"

From Boolean Functions
Jump to: navigation, search
(Created page with "= Characterization of Permutations = == Component Functions == An <math>(n,n)</math>-function <math>F</math> is a permutation if and only if all of its components <math>F_\l...")
 
m
 
(One intermediate revision by the same user not shown)
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 =
 +
==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<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.
  
 
== 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