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 59--83, 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 1-3, 273-288"

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 ( L4-norm )plays a major role in our approach :
 nb cl. L4-norm 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 L4-norm 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 (q-1)
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 (q-1) - L( S1 0)
By average, there exists w such that :
sum_{ w in W* } L( S1, w) = ( 2 q^3 (q-1) - 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 (q-1) - L( S2 0)
By average, there exists w such that :
sum_{ w in W* } L( S2, w) = ( 2 q^3 (q-1) - 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 35-bits 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 L4-norm 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 L4-norm 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 APN-extensions 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.

The classification of APN cubics can be achieved by following (in this order) the above steps :
[ types ]   [ 13 affine classes ]
• We may assume there is at least one not quadratic bent functions. ( check )
• component 31 : We construct all 2-spaces 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 ]
• component 32 : we construct all 2-spaces 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 Eidel-Pott 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 APN-mappings 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 APN-extensions without any quadratic components.
[ types ]   [ 24 affine classes ]   [ journal ]   [ 6 ccz classes ]
These 6 ccz classes are ccz-quadratic.
• bent index one.
• We search for APN with bent-index one having a component of type 28 without any quadratic components.
[ no solution ]   [ 1 day ]
• We search for APN with bent-index 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 bent-index 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 ccz-quadratic !!
• 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.