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.


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..


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.


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.


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.

Philippe Langevin, Last modification March 29th 2012.