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 Fb : x → < b, F(x) >. We define the space of components of F

component(F) := Fb, 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)

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*.

profile of a quadratic map

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 /

conjecture I : A quadratic (8,8)-APN is an exension of a bent space !

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 ! 

     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. We identify [ christoff ??? ] maps.

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 ?

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).

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

last step

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.