8-bit bent function

This page reports our numerical experiments related to the generation of bent functions, started winter 2024 with Valerie Gillot under a suggestion of Alexandr Polujan, in order to check a conjecture regarding the normality of 8-bit bent functions.

8-bit bent function

In the paper 
Langevin, P., Leander, G. 
Counting all bent functions in dimension eight 99270589265934370305785861242880.
Des. Codes Cryptogr. 59, 193–205 (2011).
DOI:https://doi.org/10.1007/s10623-010-9455-z
We described a methode to count the number of 8-bit bent functions. The main goal of that numerical experiment is to recompute the preclass of 8-bit bent functions that we used to find that big number !

From this preclassifiction, one deduces a numerical confirmation :
8-bit bent function are regular or weakly regular ! 

V. Gillot, P. Langevin, A. Polujan
On the normality of Boolean function
submitted to BFA, (2024).
see also

bent function

Let m = 2t be a even integer. The space of Boolean functions from GF(2)^m into GF(2) is denoted by Boole(m). The Walsh coefficient of f in Boole(m) at a in GF(2)^m is the Fourier coefficient of Xof := (-1)^f at a :

W(f,a) = sum_{x in GF(2)^m } X( f(x) + a.x )

The Boolean function f is bent if and only the absolute value of its Walsh coefficients are constant equal to 2^t. From the paper : 

Result on Bent Function
Journal of Combinatorial Theory, Series A
Volume 80, Issue 2, November 1997, Pages 232-246
[ https://doi.org/10.1006/jcta.1997.2804 ]

S-type, bentable...

AGL(8,2) acts on bent functions. A bent function f in B(8) has degree less or equal to 4. For f in RM(4,8), we consider the decomposition f = h + c where h is the homogeneous part of degree 4 and c the cubic part. We call h the header of f, and we say that f has type S-N iff the GL(8,2) stabiliser of h has order N. We say a homogeneous quartic form is bentable, if there exists a cubic c such that h+c is bent. We know there are 999 GL-classes of homogeneous quartic, 536 of them are bentable.

duality, complement

The ANF of a quartic form h :
h( X ) = sum_{S} a_S X_S,   #S = 4
Denoting by c(S) the complementary of the set S in {1,2,...,8}, one defines the complementary of h by :
ch( X ) = sum_{S} a_{c(S)} X_S
It is well known that the header of the dual of f is the complementary of the header of f.
Up to duality, there are 418 classes of bentable quartics.

quadratic system

we know that if f = sum_U a_U X_U is bent then for all T of cardinality greater or equal to t+2 the coefficients of the ANF of f satisfy the sytem of quadratic equations :
sum_{ R | S = T } a_R a_S = 0

where the sum is over the {R,S} such that the union of R and S is equal to T.
In the case m=8, we gather these equations in 3 systems : S4, S3, S2 where S4 is a quadratic equation on term of degree 4 corrresponding to T={1,2,..,8}, S3 8 equations implying terms of degree 3 corresponding to the T of cardinality 7, and S2 the 28 other equations.
For an homogeneous quartic h solution of S4, we determine the bent solutions
h (quartic) + c (cubic) + q (quadric)
In that process, we use the stablizer of h to eliminate obvious symmetries. At this stage, we obtain a set of 2^27.9 bent functions which is a covering set of bent functions :
For each bent function f, there exists a bent function g in that set and an affine transformation s such that :
g = f o s + lower term of degree less or equal to 1

classification

The computation provides a cover set of bent functions under the action of AGL(8,2). Boolean function that are not in the same file (bucket) are not equivalent. Two Boolean function in the same bucket corresponding to a quartic h may be equivalent by an element of the stabilizer of h. One need to filter the bucket to eliminate redundancy...

The cover set contains 190089425=approx=2^27.62 of bent functions in 415 buckets.

data

The bent-zip directory contains files of bent functions in zipped format : nothing to do with the usual zip format. In zipped format, an 8-bit function is encoded on 32 Bytes, whence a filesize divided 32 is nothing but the number of bents in the file. One may use the C-source unzip.c to build a command to output samples of bent functions from a zip file. 

pl@fedora/bent> ./unzip.exe  -a  -l1  ~/web-docs/data/bent/bent-1.zip

anf=ab+bc+bd+acd+be+ce+bcde+af+abf+df+abdf+ef+bef+acef+def+bg+abg+cg+acg+bcg+cdg+ceg+deg+afg+bfg+bdfg+cdfg+befg+h+ah+bh+abh+dh+adh+cdh+aeh+adeh+fh+afh+abfh+agh+abgh+cgh+cdgh+egh+aegh+fgh
#1 bent found...

pl@fedora/bent> ./unzip.exe  -x  -l2 -r3   ~/web-docs/data/bent/bent-1.zip

x_1x_3+x_1x_4+x_1x_5+x_2x_5+x_4x_5+x_2x_3x_4x_5+x_1x_6+x_2x_6+x_1x_3x_6+x_2x_3x_6+x_1x_2x_4x_6+x_3x_5x_6+x_1x_3x_5x_6+x_4x_5x_6+x_1x_7+x_1x_2x_7+x_3x_7+x_1x_3x_7+x_2x_3x_7+x_4x_7+x_2x_4x_7+x_3x_4x_7+x_5x_7+x_1x_5x_7+x_2x_5x_7+x_3x_5x_7+x_6x_7+x_1x_6x_7+x_2x_4x_6x_7+x_3x_4x_6x_7+x_2x_5x_6x_7+x_8+x_2x_8+x_1x_2x_8+x_3x_8+x_1x_4x_8+x_3x_4x_8+x_5x_8+x_1x_5x_8+x_1x_4x_5x_8+x_1x_2x_6x_8+x_7x_8+x_1x_7x_8+x_1x_2x_7x_8+x_3x_4x_7x_8+x_5x_7x_8+x_1x_5x_7x_8

x_1x_3+x_2x_3+x_2x_4+x_1x_3x_4+x_1x_5+x_2x_5+x_4x_5+x_2x_3x_4x_5+x_1x_6+x_2x_6+x_3x_6+x_2x_3x_6+x_1x_4x_6+x_1x_2x_4x_6+x_5x_6+x_1x_3x_5x_6+x_1x_7+x_1x_2x_7+x_3x_7+x_1x_3x_7+x_4x_7+x_5x_7+x_2x_5x_7+x_3x_5x_7+x_1x_6x_7+x_2x_6x_7+x_2x_4x_6x_7+x_3x_4x_6x_7+x_2x_5x_6x_7+x_8+x_2x_8+x_3x_8+x_1x_4x_5x_8+x_1x_2x_6x_8+x_2x_7x_8+x_1x_2x_7x_8+x_4x_7x_8+x_3x_4x_7x_8+x_5x_7x_8+x_1x_5x_7x_8+x_6x_7x_8
#2 bent found...

pl@fedora/bent> ./unzip.exe  -t  -l1    ~/web-docs/data/bent/bent-1.zip

TT= 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 1
#1 bent found...
[ data ] [ bent zip file ]
Philippe Langevin,
Institut Mathématiques de Toulon,
last modification : june 2024.