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

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 , 𝐹 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 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 n=4} :

Let 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 F\in\mathbb{F}_{2^n}[x]} be a permutation polynomial with 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 n=2m} . Then:

1. 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 n=4} , then 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 F} is not APN.

2. 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 F\in\mathbb{F}_{2^m}[x]} , then 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 F} is not APN.