APN Permutations

From Boolean
Revision as of 13:29, 23 September 2019 by Ivi062 (talk | contribs)
Jump to navigation Jump to search

Characterization of Permutations

Component Functions

An [math]\displaystyle{ (n,n) }[/math]-function [math]\displaystyle{ F }[/math] is a permutation if and only if all of its components [math]\displaystyle{ F_\lambda }[/math] for [math]\displaystyle{ \lambda \in \mathbb{F}_{2^n}^* }[/math] are balanced.

Autocorrelation Functions of the Directional Derivatives

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

[math]\displaystyle{ \sum_{a \in \mathbb{F}_{2^n}^*} \mathcal{F}(D_af_\lambda) = -2^n }[/math]

for any [math]\displaystyle{ \lambda \in \mathbb{F}_{2^n}^* }[/math].

Equivalently [1], [math]\displaystyle{ F }[/math] is a permutation if and only if

[math]\displaystyle{ \sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}(D_af_\lambda) = -2^n }[/math]

for any [math]\displaystyle{ \lambda \in \mathbb{F}_{2^n}^* }[/math].

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 n 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 [math]\displaystyle{ (n,n) }[/math]-function [math]\displaystyle{ F }[/math] is an APN permutation if and only if [1]

[math]\displaystyle{ \sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}(D_af_\lambda) = -2^n }[/math]

and

[math]\displaystyle{ \sum_{\lambda \in \mathbb{F}_{2^n}^*} \mathcal{F}^2(D_af_\lambda) = 2^{2n} }[/math]

for any [math]\displaystyle{ a \in \mathbb{F}_{2^n}^* }[/math].

  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