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
42621441.0012, 21, 28, 33
26062082.312, 6
56553602.509, 13, 19, 23, 29
28028163.061, 5
18519683.2511
19994243.810
710485764.008, 10, 17, 20, 22, 26, 32
111960324.564
314417925.507, 15, 27
118350087.0016
119824647.563
122282248.5018
126214401025
1301465611.5014
1419430416.0031
1576716822.0024
11677721664.0030
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.

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 :

Remarkable facts


Philippe Langevin, Last modification February 21th 2012.