Classification of APN cubics in dimension 6 over GF(2)
This page reports the numerical experiments related to the classification of
the almost perfect nonlinear cubics in 6 variables that I computed 2011/2012.
The details will be in a forthcoming paper, a joint work with Elif and Zulfukar
Saygi. Many thanks to Yves Edel for the helpful comments that enable us to
correct some mistakes in our classification process.
Objectives
Let m be a positive integer. A mapping is a vectorial function from
GF(2)^m into GF(2)^m. A mapping f is said to be almost perfect
nonlinear 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
affine and ccz classes of APN cubics in dimension 6.
The method used
to classify APN mappings in dimension 5 can not be applied in this situation because
the running time of the computation of Fourier transforms in dimension >32 cost
too much time.
main result
It is well known there are 13 affine classes of quadratic APN. In
the paper :
A new almost perfect nonlinear function which is not quadratic
Advances in Mathematics of Communications pp 5983, 3, 2009.
Alexander Pott and Yves Edel discovered a new ccz class represented
by a cubic mapping i.e. a cubic APN which is not ccz quadratic.
In
On the classification of APN functions up to dimension five
Designs, Codes and Cryptography Volume 49, Numbers 13, 273288"
Marcus Brinkmann and Gregor Leander give also 14 ccz classes
of APNs, 13 are quadratic + 1 cubic. The cubics APNs of these
papers are ccz equivalent.
Our numerical experimentation complete these works by showing
the list of non ccz quadratic APN cubics is complete !
Boolean cubics
The classification of Boolean cubics of 6 variables is resumed in this file [
cubics.dat ]. There
are 34 classes, 4 are bent (type 12,21,28,33 ) , 4 are quadratic (30,31,32,33). The
distribution of moments of order 4 of Walsh spectra ( L4norm )plays a major
role in our approach :
nb cl. 
L4norm 
factor 
type 
4  262144  1.00  12, 21, 28, 33 
2  606208  2.31  2, 6 
5  655360  2.50  9, 13, 19, 23, 29 
2  802816  3.06  1, 5 
1  851968  3.25  11 
1  999424  3.81  0 
7  1048576  4.00  8, 10, 17, 20, 22, 26, 32 
1  1196032  4.56  4 
3  1441792  5.50  7, 15, 27 
1  1835008  7.00  16 
1  1982464  7.56  3 
1  2228224  8.50  18 
1  2621440  10  25 
1  3014656  11.50  14 
1  4194304  16.00  31 
1  5767168  22.00  24 
1  16777216  64.00  30 
The smallest L4norm is q^3 = 262144 (bent function). The second value is
606208 = 2.31 q^3 and it corresponds to type 2 and 6.
L4 norm trick
We denote by L4( g ) the moments of order four of a Boolean mapping g.
A mapping f from GF(2)^m into GF(2)^m is APN if and only if
sum_{ b in GF(2,m)* } L4( b.f ) = 2 q^3 (q1)
where b.f is the Boolean component x>b.f(x). The above relation implies the
existence of a component f such that L4(f) <= 2*q^3 that is two times
the moment of a bent function. In dimension 6, the cubics having
a moment less or equal to 2*q^3 are precisely the bent functions. More
precisely, if f is an APN cubic mapping then at least 16 of its components
are bent, and the rank of the bent component is at least 5.
Let S be a space of Boolean functions,
given a Boolean function t, we define :
L(S, t) = sum_{ 0 != g in t + S } L4( g ).
We denote by V(f) the space of components of f. As we see there is
a bent component s1 in V(f). Let W a supplementary of s1, denoting
by S1 the sapce generated by s1, we have :
sum_{ w in W* } L(S1, w ) = 2 q^3 (q1)  L( S1 0)
By average, there exists w such that :
sum_{ w in W* } L( S1, w) = ( 2 q^3 (q1)  L( S1, 0) ) / ( q/2  1 )
One can check that one of w or w+s is a bent function s2. Denoting
by S2 the space generated by s1 and s2, considering a supplementary
W of S2, we have :
sum_{ w in W* } L(S2, w ) = 2 q^3 (q1)  L( S2 0)
By average, there exists w such that :
sum_{ w in W* } L( S2, w) = ( 2 q^3 (q1)  L( S2, 0) ) / ( q/4  1 )
One can check that one of w+S2 is a bent function s3. This can be
repeated at least 4 times to obtain a system bent functions of rank 5
in V( f ).
Tools
We implement several tools to manage sets mappings
from GF(2)^m into GF(2)^l i.e set of mappings at level l,
often called (m,l)mappings. These
implementations are based on a representation of the cubics as 35bits vectors,
the type of the cubics is stored in a large table of 2^35 bytes.
 select : used at level 0, it initializes a set of (6,1)mappings of choosen type.
 space : used at level 1, it extenteds a set of (6,2)mappings using component of a given type.
 bent : used at level 1 or 2, it builds a set of (6,l+1)bent mappings from a set of (6,l)bent mappings.
 cover : build the (6,l+1)mappings satisfying L4norm trick from a set of (6,l)mapping using
fixator at level l to avoid affine equivalent mappings.
 group : computes the fixator groups of a set of (6,l)mapping useful for cover.
 fast : buid the (6,l+1)mappings satisfying L4norm trick from a set of (6,l)mappings,
a thread version of cover, useful at level 3, 4, 5 when fixator group are small or trivials.
 filter : eliminate affine equivalence redundancies in a set of (6,l)mappings.
 clean : eliminate mappings that can not be extented in a APN mapping because of obvious reasons.
 check : used at level 4 or 5, it eliminates mappings that can not be extented in a APN mapping after trying backtrack search
 apn : used at level 4 or 5, it gives the APNextensions of a set of (6,l)mappings.
 ccz : used at level 6, eliminate ccz equivalence redundancies.
Baby example
To illustrate our tools, we prove the non existence of
APN mappings of degree greater or equal to 4 having a
quadratic component space of dimension 3.
Leitfaden
The classification of APN cubics can be achieved
by following (in this order) the above steps :
 quadratic components.
 pure quadratic. Quadratic apns are knowns:
[ types ]
[ 13 affine classes ]
 We may assume there is at least one not quadratic
bent functions. ( check )
 component 31 :
We construct all 2spaces with a component 31,
and a component of type 12, 21 or 28.
We determine all the APN extensions.
[ types ]
[ 3 affine classes ]
[ journal ]
[ 1 ccz class ]
This class is cczquadratic.
 component 32 :
we construct all 2spaces with a component 32,
and a component of type 12, 21 or 28.
we determine all the APN extensions without
components of type 31.
[ types ]
[ 494 affine classes ]
[ journal ]
[ 14 ccz classes ]
i.e. 13 quadratic classes + the EidelPott class.
 component 33 :
we determine APN without components of type 31,
32, but at least one component of type 33.
[ no solution !! ]
[ journal ]
 bent index three. We serach APNmappings with bent index three without any quadratic component.
[ no solution ! ]
[ journal ]
 bent index two.
 There are 24 affine classes of bent spaces of dimension 2, without quadratic component.
 we determine all the APNextensions without any quadratic components.
[ types ]
[ 24 affine classes ]
[ journal ]
[ 6 ccz classes ]
These 6 ccz classes are cczquadratic.
 bent index one.
 We search for APN with bentindex one having a component of type 28
without any quadratic components.
[ no solution ] [ 1 day ]
 We search for APN with bentindex one having a component of type 21
without any quadratic components nor component of type 28.
[ no solution ]
[ 4 weeks ]
 We terminate the classification by searching for the APN cubics having bentindex one but without any quadratic components nor bent components of type 21 or 28.
[ no solution ]
[ 3 weeks ]
Remarkable facts
 At the end, we get :
[ 534 affine classes ]
 Only one class is not cczquadratic !!
 Only one ccz class contains a permutation :(
 All the solution have bent rank 6

The components of APN cubics have quadratic type I i.e. Their Fourier coefficients are multiple of 8.

For all counting function
n_u (v) = #{ x  f(x+u)+f(x) = v } > 0,
there exists w !=0 such that
n_u( v + w ) = nu_( v) for all v.
 Curiousely, No solution with a quadratic component space of dimension 4.
Philippe Langevin, Last modification February 21th 2012.