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.