profile of quadratic APN maps

profile of quadratic APN in dimension 8

This page reports some numerical data related the construction of quadratic APN in 8 variables we started in Autumn 2023 with Alexander Polujan, Christof Beierle, Gregor Leander and Nikolay Kaleyski.

https://who.paris.inria.fr/Leo.Perrin/slides/bfa-2021.pdf

space of components

Let m,n be a positive integers. An (m,n) maps F is a mapping from GF(2)^m into GF(2)^n. Each b in GF(2)^m provides a Boolean function F_b : x → < b, F(x) >. We define the space of components of F

component(F) := F_b, b in GF(2)^n

almost perfect nonlinear

An (m,m)-map is called APN if for all distinct x, y, z, t in GF(2)^m

x+y+z+t = 0 implies F(x) + F(y) + F(z) + F(t) ≠ 0

quadratic APN

The quadratic APN in dimension 8 are legion. The project started with the knowledge of 32892 class of quadratic APN under the conjectural existence of more than 50000 by Léo Perrin.

32892 known APNs

The present project provides tools to construct new quadratic APNs. At the end of january 2024, we reach the construction of 511583 classes of APNs, and most of them are new. Now, we have more than 2 millions of classes...

[project] [last update]
last update : about 2 millions of APNs

definition

For a quadratic form f, we denote by alpha(q) the sum of the fourth-momentr of the Walsh coefficients of f, divided by q^3 (normalisation). If f is bent then alpha(f) = 1. In dimension 8, alpha(f) takes the values 1, 4, 16, 64 according to the dimension of the radical of f.

It is well known that a (m,m)-mapping F is APN iff sum_{f in compo(F) } alpha(f) = 2 (q-1)

dual equivalence

Observing B(28) the space of quadratic forms, one can see that F is a quadratic APN if and only if the intersection of the set 2-rank quadratic form (almost linear quadratic form) and the space comp(F) ) is empty.

How to construct a space of dimension 20 in B(28) not intersecton the set of 2-rank quadratic form ?

random serach

type quadratic APN

The rank distribution of components of known quadratic APN takes only 6 values :

  27442 #class    170  85   0   0  
   4913 #class    174  80   1   0
    361 #class    178  75   2   0
    146 #class    182  70   3   0
     26 #class    186  65   4   0
      4 #class    190  64   0   1

Lemma I : the rank distribution of any quadratic APN is one of the 6 above type.

extension

An extension of a mapping (m,r)-mapping F is a (m,s)-mapping G such that component( F ) is a subspace of component( G ).

In that project, we want construct all the APN satisfying conjecture I starting from the classification of bent space by Pott and Polujan. There are 92515 classes of bent spaces and the task promizes to be hard but feasable !

conjecture II : A quadratic (8,8)-APN is an exension of a bent space !
conjecture III : APN of extension of a quadratic (8,7) is quadratic

profile of a quadratic map

Given a subspace V of quadratic form in 8 variables, we denote by BS( V ) the pair (b,s) where b in the number of bents in V and s the sum of the alpha(f) on V*.

We define the profile P(F) of a (8,8)-quadratic map to be the greatest tuple in lexical order :

[ BS( V1 ) , BS(V2) , ... , BS(V8) ] where (V0, V1, V2, ..., V8) ranges the flags of compo(F) i.e. a chain of distinct subspace included in compo(F).

profile of known APNs

      
#number of maps : 32892
      9 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 28 40 / 50 102 /
    468 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 28 40 / 52 96 /
     90 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 28 40 / 54 90 /
     32 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 50 102 /
   3128 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 52 96 /
      7 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 54 102 /
  13480 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 54 90 /
      2 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 56 108 /
   7549 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 56 84 /
     49 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 56 96 /
   7008 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 58 78 /
     80 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 58 90 /
    923 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 60 72 /
     67 profile: 0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 60 84 /

     0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 58 
     0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 60

In a warm up stage, we computed all the APNs with the above profile identifying 7334 quadratic APN whose rank distribution :

   5528 #class    0 170  85   0   0
   1562 #class    0 174  80   1   0
    169 #class    0 178  75   2   0
     56 #class    0 182  70   3   0
     13 #class    0 186  65   4   0
      6 #class    0 190  64   0   1

We also completed the search of APNs with profile :

     0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 56

The search of APNs with profile :

     0 0 / 1 1 / 3 3 / 7 7 / 15 15 / 30 34 / 54

provides a huge number of solutions, the computation are till in progress... We already identified more than 3,500,000 ccz class of quadratic APNS...

estimation

On the basis of that numerical approach 4,500,000 seems to be a good estimation of the number ccz class.

permutation

Unlike case of dimension 6, there seems to be an obstruction to the existence of a permutation ccz equivalent to a quadratic APN.

decision problem

Let t < m
Let F be a (m,m-t) map.
Let V be a subspace of dimension K in B(m)
is there an APN-extension of F with component in V ?
Let f_i a basis of V
Let Z(F) be the set of {x,y,z,t} such that F(x)+F(y)+F(z)+F(t) = 0
one defines a code of length N := #Z(F) whose columns are indexed by the xyzt :

		f_1(x)+f_1(y)+f_1(z)+f_1(t)
		f_2(x)+f_2(y)+f_2(z)+f_2(t)
	Cxytz := 	
		...
		f_K(x)+f_K(y)+f_K(z)+f_K(t)

The decision problem is equivalent to say there exists t codewords in C whose union of support is equal to {1,2,..,N}

For any algebra A of dimension t over GF(2), the decision problem becomes

is there a codeword of length N in C[N,K] over A ?

last step

We use Gauss elimination to determine the APN-extensibilty of a (8,7)-quadratic.

algorithm

For a typical situation in dimension m=8, considering extension of (8,6)-quadratic maps, we have a set of 10^6 codes of length N = 3664 and dimension K=26 over GF(4).

Actually, we have a code that decide of the APN-extensibilty of a (8,6)-quadratic map in 0.5 sec..

To improve our search of APNs, we need a probabilist algorithm that return NO the code do not contain a codeword of lenght N or YES if it contains probably a code word of length N.

invariant

Walsh of Q

Denoting by Q1, Q2, Q3, Q4 the boolean functions of B(28) indicators of quadric of rank 8, 6, 4, and 2, their degrees :

	deg(Q1) =   4 
	deg(Q2) =  12
	deg(Q4) =  20
	deg(Q6) =  28

and the Walsh distribution are :

[112881664      4096     -4096     28672   -888832]
[149920960     -5440      5312    -33600    597184]
[  5622036      1428     -1260      4372    289044]
[    10795       -85        43       555      2603]

Walsh of A

The Fourier transform of the inegral function A that maps q of B(28) on α(q) takes three values :

	 803208960 (zero)  -256  6291200 (alinear)

again, this shows that F is a quadratic APN if and only if the orthogonal of comp(F) does not contain any almost linear function.

data

data apns files

Philippe Langevin,
Institut Mathématiques de Toulon,
last modification : april 2024.