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

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

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 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 3n} , 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} odd and 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 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

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

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}^2(D_af_\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 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} is even, no APN function exists in a class of permutations including power permutations.

Specifically:

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

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} is odd, 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 gcd(d,2^n-1)=1} and, 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} is even, 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 gcd(d,2^n-1)=3} .

Consequently, APN power functions are permutations 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} is odd, and are three-to-one over $\mathbb {F} _{2^{n}}^{*}$ 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} 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 $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.

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 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(x)=ux^3+ux^{10}+u^2x^{24},} where 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 u} is a primitive element 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 \mathbb{F}_{2^6}} . 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 equivalent to the Kim function $\kappa (x)=x^{3}+x^{10}+ux^{24}$.

The question of existence of APN permutations in even dimension 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\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 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 \mathbb{F}_{2^{n/2}}} , or in 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 \mathbb{F}_{2^4}} for 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} divisible by 4;

4. Functions whose univariate representation coefficients satisfy 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_{i=0}^{(2^n-1)/3}a_{3i}=0} ;

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