Classification of APN mappings in dimension 5 over GF(2)

This page reports the numerical experiments related to the classification of the APN mappings in 5 variables that I computed in July 2011.

### Definitions

Let m be a positive integer. A mapping is a vectorial function from GF(2)^m into GF(2)^m. More generally, a mapping at level l is a vectorial function from GF(2)^m into GF(2)^l. A mapping f is said to be APN when,

for all non zero u, all v :  #{ x | f(x+u) + f(x) = v} = 0 or 2.

The goal of the numerical experiment is to describe the set of APN mappings in dimension 5. This job was done by Brinkmann and Leander, as a consequence of
Marcus Brinkmann, Gregor Leander On the classification of APN functions up to dimension five Designs, Codes and Cryptography Volume 49, Numbers 1-3, 273-288, DOI: 10.1007/s10623-008-9194-6

The method presented here is completely different and it looks more efficient to obtain the classification of APN mappings up to CCZ-equivalence..

### AGL-equivalence

Two mappings f and g at level l are affine equivalent when there exists a linear transformations A in AG(2,l), an affine transformation B in AG(2,m) such that :

g = A o f o B + c
where c is an affine mapping at level l.
This equivalence is often called extended affine equivalence. Of course, APN property is invariant under affine equivalence.

### CCZ-equivalence

According to Charpin, Carlet and Zinoviev, two mappings f and g at level l are CCZ-equivalent when there exists an affine transformation S in AG(2,m + l),

graph( g ) = S graph(f)
where graph( g ) = { (x, g(x) ) | x in GF(2)^m } is the graph of the mapping g.
AGL-equivalence is finer than CCZ-equivalence APN property is invariant under CCZ-equivalence.

### Coding theory

Given a mapping at level l, we denote by vect(f) the space of Boolean functions spaned by the coordinate of f.

vect(f) = { a_1*f_1 + a_2*f_2 + ... + a_l*f_l | a in GF(2)^l }
and also the affine enveloppe of this code :
code( f ) = vect( f ) + RM(1, m)
where RM(1,m) is the space of affine Boolean functions.
One can prove that two mappings g and f are CCZ-equivalent iff code(f) and code(g) are equivalents.

### Character approach

Given x,y,z,t in GF(2,m), we denote by xyzt the character of B(m) that sends a Boolean function b on (-1)^[ b(x)+b(y)+b(z)+b(t) ]. We consider the indicator function M of characters X of B(m) of the form xyzt with x+y+z+t=0 but all disctincts. The Fourier coefficient of M at b is:

M*( b ) = sum_{ X } M( X ) X( b )

A mapping f is APN iff
sum_{ s in vect(f) } M*( s ) = 0
or equivalentely
sum_{ X in ortho( f ) } M( X ) = 0

Now, let f be a mapping at level l. A Boolean function b is a candidate for f if there exist an APN extension of f of the form
x -> (f(x), b(x), ... )
Up to affine equivalence, a candidate b can be choosen modulo the space code( f ) := vect( f ) + RM(1,m). Let W be a supplementary of aff( f ). m( w ) = sum_{ X in ortho( f ) } X( w ) A mapping (f,g) is APN iff
sum_{ s in vect( g ) } m*( s ) = 0
in particular there is a component of g such that
m*( w ) <= N / ( 2^(m-l) - 1 )
All the elements w satisfying the above relation are called good candidates. In particular, one can use fast Walsh Fourier transform to determine the set of good candidates. Denoting by G the stabilizer of aff( f ), one can determine the good candidates up to the action of G the work factor of that job looks like :
2^w * w * | G |, with w = 2^m - l - m + 1

### Covering lemma

A set C of mappings at level l, is a covering at level l if any APN mapping is CCZ-equivalent to (f, g) with f in C and some mapping g at level m-l. One construct a covering at level l+1 by extending the mappings f of C by Boolean functions b that are good candidates for g. One reduce the size of this new covering by applying CCZ equivalence at level l+1.

### One key point

Given a mapping at level 3 or more, it is easy to decide if it can be extented to an APN mapping by backtrack search and dancing links.

### Computation

We use 7 tools : select Boolean function with given L4 norm, extension using Fourier transform, agl-extension is the same but up to stabliser group (level 2), test checks for trivial obstruction, apn-check verifies if there exists an APN-extension (level 4), apn finds APN-extension, and ccz classifies up to CCZ-equivalence.
• Covering at level 1.
• Up to affines transformations, there are 48 Boolean functions modulo RM(1,5).
• Only 6 of these classes satisfy the L4-norm criterion, see sel-1-5.txt .
• selection --> 6, 0 immediate.
• Covering at level 2.
• agl-extension --> 3628 candidates in 4 minutes.
• test --> 3537, 1 minute.
• ccz --> 1782 classes, 3 minutes.
• Covering at level 3.
• extension --> 3437013 , 52 minutes.
• Note that was possible to reduce the running time and the size of this covering by determing some stablizer groups... But it costs also time to make programs !
• test --> 1071994, 2 minutes.
• apn-check --> 288, 18 minutes.
• ccz --> 7, 9 minutes.
• Covering at level 4.
• extension --> 75, 6 secondes.
• test --> 42, immediate.
• ccz -->4, in 18 minutes.
• Clearly, our home made ccz classifier is not efficient !
• Covering at level 5.
• apn --> 5, immediate.
• We apply CCZ equivalence to obtain the classification of APN mappings in dimension 5. We get 3 ccz-classes of APN mappings.

Philippe Langevin, Last modification March 29th 2012.