APN Permutations

Characterization of Permutations

Component Functions

An $(n,n)$-function $F$ is a permutation if and only if all of its components Failed to parse (syntax error): {\displaystyle f_λ} for $\lambda \in \mathbb {F} _{2^{n}}^{*}$ are balanced.

Autocorrelation Functions of the Directional Derivatives

For any boolean function $f$, we denote by ${\mathcal {F}}(f)$ the following value related to the Fourier (or Walsh) transform of $f$:

${\mathcal {F}}(f)=\sum _{x\in \mathbb {F} _{2^{n}}}(-1)^{f(x)}=2^{n}-2wt(f).$

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 Failed to parse (syntax error): {\displaystyle λ\in\mathbb{F}^*_{2^n}} .

Equivalently , $F$ is a permutation if and only if

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

for any $a\in \mathbb {F} _{2^{n}}^{*}$.

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 $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 $(n,n)$-function $F$ 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 $a\in \mathbb {F} _{2^{n}}^{*}$.

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.

APN Permutations and Codes

The (Hamming) weight of any vector $x\in \mathbb {F} _{2}^{n}$ is denoted by $wt(x)$, and the (Hamming) distance between any two vectors $x$ and $y$ from $\mathbb {F} _{2}^{n}$ is denoted by $d(x,y)$. Any linear subspace $C$ of $\mathbb {F} _{2}^{n}$ of dimension $k$ is called a binary linear code of length $n$ and dimension $k$ and is denoted by $[n,k,d]$, where $d$ is the minimum Hamming distance of $C$.

Any linear $[n,k,d]$ code $C$ is associated with its dual $[n,n-k,d^{\perp }]$ code, denoted by $C^{\perp }$ and defined as $C^{\perp }=\{x\in \mathbb {F} _{2}^{n}\;|\;c\cdot x=0,\;\forall c\in C\}.$

Let ${\mathcal {H}}$ be a binary $(r\times n)$ matrix. We say that a linear binary code $C$ of length $n$ is defined by the parity check matrix ${\mathcal {H}}$ if $C=\{c\in \mathbb {F} _{2}^{n}\;|\;c{\mathcal {H}}^{t}=0\},$ where ${\mathcal {H}}^{t}$ is the transposed matrix of ${\mathcal {H}}$.

Let $F:\mathbb {F} _{2^{n}}\rightarrow \mathbb {F} _{2^{n}}$ be APN, with $F(0)=0$.

$F$ is CCZ-equivalent to an APN permutation if and only if $C_{F}^{\perp }$ is a double simplex code (i.e. $C_{F}^{\perp }=C_{1}\oplus C_{2}$, where $C_{1},C_{2}$ are $[2^{n}-1,n,2^{n-1}]-$codes).

An APN Permutation in Dimension 6

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 (of algebraic degree $n-2$ and nonlinearity $2^{n-1}-2^{n/2}$) in dimension 6.

This function is CCZ-equivalent to the Kim function $\kappa (x)=x^{3}+x^{10}+ux^{24}$ (where $u$ is a primitive element of $\mathbb {F} _{2^{6}}$), whose associated code $C_{F}^{\perp }$ is therefore a double simplex code. It was used later in the cryptosystem Fides, which has been subsequently broken due to its weaknesses in the linear component.

Dillon's function is also EA-equivalent to an involution and it is studied further in the introduction of the butterfly construction. Unfortunately, this construction does not allow obtaining APN permutations in more than six variables.

The Big Open APN Problem

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.