APN Permutations: Difference between revisions
From Boolean
mNo edit summary |
mNo edit summary |
||
| Line 3: | Line 3: | ||
== Component Functions == | == Component Functions == | ||
An | 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 < | 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>, | 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 < | 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 | 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 | 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 < | for any 𝑎 ∈ 𝔽*<sub>2<sup>𝑛</sup></sub>. | ||
Revision as of 13: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
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 \sum_{a \in \mathbb{F}_{2^n}^*} \mathcal{F}(D_af_\lambda) = -2^n}
for any λ ∈ 𝔽*2𝑛.
Equivalently [1], 𝐹 is a permutation if and only 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 \sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}(D_af_\lambda) = -2^n}
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]
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 \sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}(D_af_\lambda) = -2^n}
and
for any 𝑎 ∈ 𝔽*2𝑛.
- ↑ 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
- ↑ Marco Calderini, Massimiliano Sala, Irene Villa, A note on APN permutations in even dimension, Finite Fields and Their Applications, vol. 46, 1-16, 2017
