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_λ }[/math] for [math]\displaystyle{ \lambda\in\mathbb{F}^*_{2^n} }[/math] are balanced.

Autocorrelation Functions of the Directional Derivatives

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

[math]\displaystyle{ \mathcal{F}(f)=\sum_{x\in\mathbb{F}_{2^n}}(-1)^{f(x)}=2^n-2wt(f). }[/math]

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{ λ\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{ a\in\mathbb{F}^*_{2^n} }[/math].

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 [math]\displaystyle{ 3n }[/math], with [math]\displaystyle{ n }[/math] odd and [math]\displaystyle{ gcd(n,3)=1 }[/math].

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 [math]\displaystyle{ n }[/math] 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].

On APN Power Functions

For [math]\displaystyle{ n }[/math] odd, all power APN functions and the known APN binomials are permutations. When [math]\displaystyle{ n }[/math] is even, no APN function exists in a class of permutations including power permutations.

Specifically:

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

If [math]\displaystyle{ n }[/math] is odd, then [math]\displaystyle{ gcd(d,2^n-1)=1 }[/math] and, if [math]\displaystyle{ n }[/math] is even, then [math]\displaystyle{ gcd(d,2^n-1)=3 }[/math].

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

APN Permutations and Codes

Any linear subspace [math]\displaystyle{ C }[/math] of [math]\displaystyle{ \mathbb{F}_2^n }[/math] of dimension [math]\displaystyle{ k }[/math] is called a binary linear code of length [math]\displaystyle{ n }[/math] and dimension [math]\displaystyle{ k }[/math] and is denoted by [math]\displaystyle{ [n,k,d] }[/math], where [math]\displaystyle{ d }[/math] is the minimum Hamming distance of [math]\displaystyle{ C }[/math].

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

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

APN (and AB) properties were expressed in terms of codes in . In particular, we mention the following result:

Theorem. Let [math]\displaystyle{ F }[/math] be a function on [math]\displaystyle{ \mathbb{F}_{2^m} }[/math] such that [math]\displaystyle{ F(0) = 0 }[/math] and let [math]\displaystyle{ C_F }[/math] be the [math]\displaystyle{ [2^m − 1,k,d]- }[/math]code defined by the parity check matrix

[math]\displaystyle{ \mathcal{H}_F=\begin{pmatrix} 1 & \alpha & \alpha^2 & \cdots & \alpha^{2^m-2}\\ F(1) & F(\alpha) & F(\alpha^2) & \cdots & F(\alpha^{2^m-2}) \end{pmatrix} }[/math]

where each entry is viewed as a binary vector and [math]\displaystyle{ \alpha }[/math] is the primitive element of [math]\displaystyle{ \mathbb{F}_{2^m}. }[/math] Then:

1. The code [math]\displaystyle{ C_F }[/math] is such that [math]\displaystyle{ 3 \leq d \leq 5 }[/math].

2. [math]\displaystyle{ F }[/math] is APN if and only if [math]\displaystyle{ d = 5 }[/math].

3. [math]\displaystyle{ F }[/math] is AB if and only if the weight of every codeword in [math]\displaystyle{ C_F^{\perp} }[/math] lies in [math]\displaystyle{ \{0, 2^{m-1}, 2^{m-1}\pm 2^{m-1/2}\} }[/math].

A binary linear [math]\displaystyle{ [2^k-1,k,2^{k-1}]- }[/math]code [math]\displaystyle{ C }[/math] in [math]\displaystyle{ \mathbb{F}_2^n }[/math] is called simplex. Simplex codes constitute a family of linear error-correcting or error-detecting block codes, easily implemented as polynomial codes (i.e. codes whose encoding and decoding algorithms may be conveniently expressed in terms of polynomials over a base field).

A [math]\displaystyle{ 2k- }[/math]dimensional code [math]\displaystyle{ C }[/math] is called a double simplex code if it can be written as a direct sum of two simplex [math]\displaystyle{ [2^k-1,k,2^{k-1}]- }[/math]codes. The following result provides a connection between APN permutations and double simplex codes:

Theorem. Let [math]\displaystyle{ F:\mathbb{F}_{2^n}\rightarrow\mathbb{F}_{2^n} }[/math] be APN, with [math]\displaystyle{ F(0)=0 }[/math].

[math]\displaystyle{ F }[/math] is CCZ-equivalent to an APN permutation if and only if [math]\displaystyle{ C_F^{\perp} }[/math] is a double simplex code, i.e. [math]\displaystyle{ C_F^{\perp}=C_1\oplus C_2 }[/math], where [math]\displaystyle{ C_1, C_2 }[/math] are simplex [math]\displaystyle{ [2^n-1,n,2^{n-1}]- }[/math]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 [math]\displaystyle{ n=4 }[/math]:

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

1. If [math]\displaystyle{ n=4 }[/math], then [math]\displaystyle{ F }[/math] is not APN.

2. If [math]\displaystyle{ F\in\mathbb{F}_{2^m}[x] }[/math], then [math]\displaystyle{ F }[/math] 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 [math]\displaystyle{ n-2 }[/math] and nonlinearity [math]\displaystyle{ 2^{n-1}-2^{n/2} }[/math]) in dimension 6.

This function is CCZ-equivalent to the Kim function [math]\displaystyle{ \kappa(x)=x^3+x^{10}+ux^{24} }[/math] (where [math]\displaystyle{ u }[/math] is a primitive element of [math]\displaystyle{ \mathbb{F}_{2^6} }[/math]) and it is given by the polynomial

[math]\displaystyle{ g(x)=w^{45}x^{60}+w^{41}x^{58}+w^{43}x^{57}+w^{4}x^{56}+w^{50}x^{54}+w^{20}x^{53}+w^{45}x^{52}+w^{20}x^{51}+w^{23}x^{50}+w^{36}x^{49}+w^{56}x^{48}+w^{21}x^{46}+w^5x^{45}+w^{21}x^{44}+w^{28}x^{43} }[/math] [math]\displaystyle{ +w^3x^{42}+w^{59}x^{41}+w^{58}x^{40}+w^{57}x^{39}+w^{53}x^{38}+w^{37}x^{37}+w^{40}x^{36}+w^{18}x^{35}+w^{41}x^{34}+w^{54}x^{33}+w^3x^{32}+w^{49}x^{30}+w^{41}x^{29}+w^{42}x^{28} }[/math] [math]\displaystyle{ +w^{50}x^{27}+w^{53}x^{26}+w^{58}x^{25}+w^9x^{24}+x^{23}+w^{28}x^{22}+w^3x^{21}+w^{21}x^{20}+w^{52}x^{19}+w^{60}x^{17}+w^{59}x^{16}+w^{10}x^{15}+w^{42}x^{13}+w^8x^{12} }[/math] [math]\displaystyle{ +w^{35}x^{11}+w^{44}x^{10}+w^{45}x^8+w^8x^7+w^{61}x^6+w^{59}x^5+w^{20}x^4+w^{12}x^3+w^{37}x^2+w^2x }[/math]

where [math]\displaystyle{ w=u^{-2} }[/math].

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 [math]\displaystyle{ n\geq 8 }[/math] 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 [math]\displaystyle{ \mathbb{F}_{2^{n/2}} }[/math], or in [math]\displaystyle{ \mathbb{F}_{2^4} }[/math] for [math]\displaystyle{ n }[/math] divisible by 4;

4. Functions whose univariate representation coefficients satisfy [math]\displaystyle{ \sum_{i=0}^{(2^n-1)/3}a_{3i}=0 }[/math];

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