APN Permutations

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 , [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. 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

[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].