APN Permutations

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

$\sum _{a\in \mathbb {F} _{2^{n}}^{*}}{\mathcal {F}}(D_{a}f_{\lambda })=-2^{n}$

for any λ ∈ 𝔽*_2^𝑛.

Equivalently , 𝐹 is a permutation if and only if

$\sum _{\lambda \in \mathbb {F} _{2^{n}}^{*}}{\mathcal {F}}(D_{a}f_{\lambda })=-2^{n}$

for any λ ∈ 𝔽*_2^𝑛.

Characterization of APN Permutations

Up to CCZ-equivalence, all of the APN permutations known so far belong to a few families, namely:

1. APN monomial functions in odd dimension.

2. One infinite family of quadratic polynomials in dimension $3n$, with $n$ odd and $gcd(n,3)=1$.

3. Dillon's permutation in dimension 6.

4. Two sporadic quadratic APN permutations in dimension 9.

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

$\sum _{\lambda \in \mathbb {F} _{2^{n}}^{*}}{\mathcal {F}}(D_{a}f_{\lambda })=-2^{n}$

and

$\sum _{\lambda \in \mathbb {F} _{2^{n}}^{*}}{\mathcal {F}}^{2}(D_{a}f_{\lambda })=2^{2n}$

for any 𝑎 ∈ 𝔽*_2^𝑛.

On APN Power Functions

For $n$ odd, all power APN functions and the known APN binomials are permutations. When $n$ is even, no APN function exists in a class of permutations including power permutations.

Specifically:

If a power function $F(x)=x^{d}$ over $\mathbb {F} _{2^{n}}$ is APN, then for every $x\in \mathbb {F} _{2^{n}}$ we have $x^{d}=1$ if and only if $x^{3}=1$, that is, $F^{-1}(1)=\mathbb {F} _{4}\cap \mathbb {F} _{2^{n}}^{*}.$

If $n$ is odd, then $gcd(d,2^{n}-1)=1$ and, if $n$ is even, then $gcd(d,2^{n}-1)=3$.

Consequently, APN power functions are permutations if $n$ is odd, and are three-to-one over $\mathbb {F} _{2^{n}}^{*}$ if $n$ is even.

The Big Open APN Problem

In his paper , Hou conjectured that APN permutations did not exist in even dimension. He proved the following theorem that covers the case of $n=4$:

Let $F\in \mathbb {F} _{2^{n}}[x]$ be a permutation polynomial with $n=2m$. Then:

1. If $n=4$, then $F$ is not APN.

2. If $F\in \mathbb {F} _{2^{m}}[x]$, then $F$ is not APN.

The question of whether APN permutations exist in even dimension was a long-standing problem until, in 2009, Dillon presented an APN permutation in dimension 6.

That is the function $F(x)=ux^{3}+ux^{10}+u^{2}x^{24},$ where $u$ is a primitive element of $\mathbb {F} _{2^{6}}$. $F$ is CCZ-equivalent to the Kim function $\kappa (x)=x^{3}+x^{10}+ux^{24}$.

The question of existence of APN permutations in even dimension $n\geq 8$ remains open. There exist nonexistent results within the following classes:

1. Plateaued functions (when APN, they have bent components);

2. A class of functions including power functions;

3. Functions whose univariate representation coefficients lie in $\mathbb {F} _{2^{n/2}}$, or in $\mathbb {F} _{2^{4}}$ for $n$ divisible by 4;

4. Functions whose univariate representation coefficients satisfy $\sum _{i=0}^{(2^{n}-1)/3}a_{3i}=0$;

5. Functions having at least one partially-bent component.