KERNELS AND DEFAULTS

PHILIPPE LANGEVIN AND PATRICK SOLÉ

Abstract. We consider the metric space of the set of boolean functions from a space over the field with two elements provided of the Hamming distance. The non-linearity of a boolean function is equal to its distance from the space of affine boolean functions. The functions having maximal non-linearity are called the bent functions. In this paper, we generalize the well known notions of kernels and defaults of the theory of quadratic forms, and we apply these notions to the study of the non-linearity of the cubic functions.

1. Boolean functions

Let E be a space of finite dimension m over the finite field 𝔽_{2}. The set of functions from E into 𝔽_{2} is denoted by 𝔽_{2}^{E}, an element of 𝔽_{2}^{E} is a boolean function. Let f be a boolean function, the set {x ∈ E | f(x) = 1} is the support of f, it is denoted by supp(f). Conversely, for any subset X of E, the indicating function 1_{X} is the unic boolean function whose support is X. With the operations inherited of the field 𝔽_{2}, the set of boolean function is a 𝔽_{2}-algebra isomorphic to the algebra of subsets of E with the operations Δ and ∩. If x_{1}, x_{2}, …, x_{m} is any basis of the dual of E then the map sending a polynomial p of 𝔽_{2}[X_{1}, X_{2}, …, X_{m}] to the boolean function p(x_{1}, x_{2}, …, x_{m}) defines an epimorphism of algebras which the kernel is the ideal generated by the polynomials X_{i}^{2} − X_{i}. Hence, the algebra 𝔽_{2}^{E} is isomorphic to the quotient 𝔽_{2}[X_{1}, X_{2}, …, X_{m}]/(X_{1}^{2}−X_{1}, X_{2}^{2}−X_{2}, …, X_{m}^{2}−X_{m}). The degree of a boolean function f, denoted by deg(f), is the smallest integer k such that f has an antecedent of degree k by the morphism above. This definition does not depend on the choice of the basis, moreover

Proposition 1. The space RM(k, m) of boolean functions of degree at most k is generated by the indicating functions of the supports of the affine varieties of codimension k. In other words, if f has degree less than k then there exits N affine varieties of codimension k V_{1}, V_{2}, …, V_{N} such that f = ∑_{i=1}^{N} 1_{V_{i}}.

Proof. This is a result by Delsarte [3]. One can see it as a consequence of the fact that the Reed-Muller codes are the only codes invariant under the action of the general affine group, see also [11].

The weight of f, denoted by wt(f), is equal to the cardinality of the support of f. The Hamming distance between two function f and g is the weight of f + g. The minimal distance between f and any affine function from E into 𝔽_{2} is the non-linearity of f, that is :

Key words and phrases. boolean functions, Reed-Muller codes, covering radius.

δ(f) = inf_{ϕ} wt(f + ϕ).

The maximal value of δ(f), when f ranges the set of boolean function, is the covering radius of the first order Reed-Muller code. It is denoted by ρ(m), a function with non-linearity ρ(m) is a bent function. These functions have a great importance for cryptographic applications, see [14, 6].

2. Characters

Let (a, b) ↦ a.b be a symmetric non-degenerate bilinear symmetric form. Let χ be the non trivial additive character of the field 𝔽_{2} : χ(0) = 1 and χ(1) = −1. The set of boolean functions is embedded in the set of complex function by the mapping f ↦ f_{χ}, where f_{χ}(x) = χ(f(x)) = (−1)^{f(x)}. The Fourier transform of the complex function h is the complex function defined by

ĥ(a) = ∑_{x∈E} h(x)χ(a.x).

Par abus de langage, we say that f̂_{χ} is the Fourier transform of f. The relation :

wt(f(x) + a.x + b) = 2^{m−1} − \frac{χ(b)}{2}f̂_{χ}(a), (1)

shows that δ(f) = 2^{m−1} − \frac{1}{2}∥f̂_{χ}∥_{∞}. This last equality justifies the definition of spectral radius of the set of affine functions, that is :

R(m) = min_{f∈𝔽_{2}^{E}} ∥f̂_{χ}∥_{∞}, (2)

so that ρ(m) = 2^{m−1} − \frac{1}{2}R(m).

For any complex function h, we have :

∑_{a∈E} ĥ(a)\overline{ĥ(a)} = 2^{m} ∑_{a∈E} h(a)\overline{h(a)} (3)

this is the famous Plancherel-Parseval identity. Its leads to the estimate

R(m) ≤ 2^{\frac{m}{2}} (4)

3. Quadrics

Let q be a quadratic form, that is a boolean function satisfying

q(x + y) = q(x) + q(y) + ϕ(x, y), (5)

where ϕ is a symetric bilinear form, the bilinear form associated to q. One defines the kernel and the default of q. [5] The kernel of q is the subspace ker(q) = {x ∈ E | ϕ(x, y) = 0, ∀y ∈ E}; Clearly, the restriction of q to its kernel is a linear form, and the default of q is the intersection ker(q)∩supp(q). Let us denote by k the dimension of the kernel of q. A straigthforward calculation show that, for any vector a in E, we have :

(6) (q̂_{χ}(a))^{2} = 2^{m} ∑_{z∈ker(q)} χ(a.z) = \begin{cases}2^{m+k}, & si a⊥ ker(q); \\ 0, & sinon. \end{cases}

On an other hand, we know that a non degenerate quadratic form has a kernel of dimension 0 if m is even, and dimension 1 if m is odd. Hence, we get the estimation

2^{\frac{m}{2}} ≤ R(m) ≤ 2^{⌈ \frac{m}{2} ⌉} (7)

which is an equality if m is even. When m is odd, the exact value of R(m) is known for m = 3, 5, 7, see [12] and [8]. Since the paper of Paterson and Wiedeman [13], we know that there exists a boolean function of RM(8, 155) which the Fourier transform has norm 216, consequently, for any odd m greater than 15 , we have :

R(m) ≤ 216 × 2^{\frac{m−15}{2}} = \frac{27}{32}2^{⌈ \frac{m}{2} ⌉} (8)

Conjecture 1. The spectral radius R(m) is equivalent to 2^{\frac{m}{2}} .

Let k be an integer, 0 ≤ k ≤ m. We define the spectral radius of the function of degree less or equal than k by R_{k}(m) = inf_{deg(f)≤k} ∥f̂∥_{∞}. The goal of that paper is to present new notions in order to study R_{3}(m). We believe that the number of cubic functions is great enough to conjecture :

Conjecture 2. The spectral radii R(m) and R_{3}(m) are asymptotically equivalent.

Note that, R_{3}(m) = R_{2}(m) holds for m less or equal to 13, see [8] and [10].

4. Kernel and defaults

In this section, we generalize the notions of kernel and default of the above section. Let v be a vector of 𝔽_{2}^{m} and let f be a boolean function. The derivation of f in the direction of v is the boolean function x ↦ D_{v}f(x) = f(x + v) + f(x). If V is a system of r vectors, say {v_{1}, v_{2}, …, v_{r}}, then the derivation in the direction of the system V is the composition D_{v_{1}} ∘ D_{v_{2}} ∘ ⋯ ∘ D_{v_{r}}. The map V ↦ D_{V} f(0) is a particular case of the combinatorial polarization of H. Ward [15]. If the vectors of V are linearly dependent then D_{V} f is equal to zero, else it is equal to the convolutional product of f by the indicating function of the support of the subspace S of 𝔽_{2}^{m} generated by V : D_{V} f(x) = 1_{S} ∗ f(x); that is the derivation of f in the direction of S, introduced by Dillon in [6]. For any vector v , we have :

D_{v}(∑_{S} a_{S} 1_{S}) = ∑_{S} a_{S} d(v, S) 1_{(v+S)∪S} (9)

where the S’s are affine spaces, and d(v, S) is equal to 1 if and only if v does not lie in the direction of S. .

Proposition 2. Let f be a boolean function; Then

∀v ∈ E, deg(D_{v}f) ≤ deg(f) − 1, et ∃v ∈ E deg(D_{v}f) = deg(f) − 1

Proof. Note that is v is not in the direction of S then the codimension of (v + S) ∪ S is equal to the codimension of S minus 1, the first point is a consequence of 1. For the second point, we may assume that, the variable x_{1} appears in a monomial of degree deg(f). Hence, f reads g(x_{2}, x_{3}, …, x_{m}) + x_{1}h(x_{2}, x_{3}, …, x_{m}) where h is a function of degree deg(f) − 1, which proves the result since D_{e_{1}}f = h.

Let r be an integer. We define the map λ^{(r)} which transforms the boolean function f defined on 𝔽_{2}^{m} in the boolean function defined over 𝔽_{2}^{m}^{r} by :

λ^{(r)}(f)[x_{1}, x_{2}, …, x_{r}] = ∑_{λ_{1},λ^{(2)},...,λ^{(r)}} f( ∑_{i=1}^{r} λ_{i}x_{i}) = D_{{v_{1},v_{2},...,v_{r}}}f(0)

Proposition 3. The restriction of λ^{(r)} to RM(r, m) is onto Λ^{r}(E), its kernel is RM(r − 1, m).

Proof. Indeed, the proposition above shows that the function x ↦ D_{{v_{1},v_{2},...,v_{r}}}f(x) is constant.

When the degree of f is equal to r, the map λ^{(r)}(f) is a r-linear map; That is

[1] the multilinear form associate to f. We define the kernel and the default of f as in the degree 2 case :

ker(f) = {(x_{1}, x_{2}, …, x_{r−1}) | λ^{(r)}(f)[x_{1}, x_{2}, …, x_{r}] = 0, ∀x_{r} ∈ E}

def(f) = {(x_{1}, x_{2}, …, x_{r−1}) | λ^{(r−1)}(f)[x_{1}, x_{2}, …, x_{r−1}] = 1}

The cardinality of ker(f) and def(f) are respectively denoted by k(f) and d(f). These numbers are affine numerical invariants : for any affine transformation T, we have

k(f) = k(f ∘ T),  et  d(f) = d(f ∘ T),

which comes from the equality, D_{v}(f ∘ T) = (D_{θ(v)}f) ∘ T, where θ is the linear map associate to the affine map T. For example, let 1 ≤ i, j, k ≤ m be three distinct integers, and consider the monomial function x_{i}x_{j}x_{k}. Its multilinear form is not zero, so that is a lift of the determinant function of the space generated by e_{i}, e_{j} and e_{k}.

λ^{(3)}(x_{i}x_{j}x_{k})[x, y, z] = det_{i,j,k}(x, y, z) = (\begin{matrix}x_{i} & y_{i} & z_{i} \\ x_{j} & y_{j} & z_{j} \\ x_{k} & y_{k} & z_{k} \end{matrix}) (10)

It follows that for any quadratic function q ∈ RM(2, 3), the function x_{1}x_{2}x_{3}+ q(x) of RM(3, 3) has no default.

5. Cubics

In [2] C. Carlet proposes to study the non-linearity of a boolean function by means of the hight order moments of its fourier transform. For example, he gives the inequality :

∑_{a∈E} (f̂_{χ}(a))^{4} ≥ 2^{3m},

which is satisfied by any boolean function. The equality occurs if and only if f is bent and m is even. In this section, we study the links between the kernel and the moments of order 4 of the Fourier transform of a cubic. We begin by two simple fact about the trilinear form of a cubic.

It is easy to check that the trilinear form of the cubic f satisfies

λ^{(3)}(f)[x, y, z] = λ^{(2)}(f)[x, y] + D_{x,y}f(z). (11)

Which leads to the main formula of this paper,

Proposition 4. If f is a boolean function of degree 3 then

∑_{a∈E} (f̂_{χ}(a))^{4} = 2^{2m}(k(f) − 2d(f)),

Proof. Indeed,

\begin{aligned}∑_{a∈E} (f̂_{χ}(a))^{4} & = 2^{m}f_{χ} ∗ f_{χ} ∗ f_{χ} ∗ f_{χ}(0) \\ & = 2^{m} ∑_{x+y+z+t=0} χ(f(x) + f(y) + f(z) + f(t)) \\ & = 2^{m} ∑_{x,y,z} χ(f(x) + f(y) + f(z) + f(x + y + z)) \\ & = 2^{m} ∑_{x,y,z} χ(f(x + z) + f(y + z) + f(z) + f(x + y + z)) \\ & = 2^{m} ∑_{x,y,z} (λ^{(3)}(f)[x, y, z] + λ^{(2)}(f)[x, y]) \\ & = 2^{2m} ∑_{(x,y)∈ker(f)} (λ^{(2)}(f)[x, y]) \\ & = 2^{2m}(k(f) − 2d(f)) \end{aligned} (12)

We say that a boolean function exceeds the quadratic bound if its nonlinearity is greater than the non-linearity of any quadratic function. Of course, this notion takes sense only is the case of odd m. From [9] and [10], we know that if m is less or equal than 13 then the cubics do not exceed the quadratic bound.

Proposition 5. Let f be a boolean function of degree 3 such that k(f) − 2d(f) ≥ 2^{m+1} then f does not exceed the quadratic bound.

Proof. That is a consequence of the following trick about meanings. Let (a_{i})_{1≤i≤n} be a sequence of n positive real numbers. Let μ be the meaning of the a_{i}’s, and let ν be the meaning of the (a_{i})^{2}’s. If ν > 2μ^{2} then there exist i such that a_{i} ≥ 2μ. Indeed, \frac{1}{n} ∑_{i=1}^{n}(a_{i} − μ)^{2} = ν − μ^{2}, and there exists i such that |a_{i} − μ| > μ, since a_{i} ≥ 0, we get a_{i} > 2μ.

Note that if f has no default then k(f) − 2d(f) = k(f) ≥ 32^{m} − 2, so :

Corollary 1. If f is cubic without default then f does not exceed the quadratic bound.

This result was obtained in [11] but only for m ≤ 19. The proposition 4 shows that in order to construct cubics far from the first order Reed-Muller code, we have to construct cubics f doing k(f) − 2d(f) small.

6. Bounds

Let f be a boolean function of degree 3. The ordered pair (x, y) ∈ 𝔽_{2}^{m} × 𝔽_{2}^{m} is in the kernel of f if and only if y is in the kernel of the quadratic function D_{x}f. Let us denote by r(x) the dimension of the kernel of the quadratic form D_{x}f. We have,

| ker(f)| = ∑_{x∈E} 2^{r(x)}. (13)

Proposition 6. Assume that m is even. If f is a boolean function of degree 3 then the kernel of f contains at least 5 × 2^{m} − 4 elements.

Proof. One remarks that the kernel of D_{x}f contains x. Hence, r(x) ≥ 2 since r(x) and m have the same parity.

Proposition 7. Assume m odd. If f is a boolean function of degree 3 then the kernel of f contains at least 3 × 2^{m} − 2 elements.

Proof. idem.

In the next section, we will see that these bound are reached when m = 3 and m = 6. The above estimate must be compared with some results of Goethals about the space of quadratic forms, [4, 7]. For any odd integer m, there exists a space of dimension m of quadratic forms of rank 0 or m − 1. For example, the space of quadratic forms x ↦ Tr_{𝔽_{2}^{m}/𝔽_{2}}(ax^{2^{t}} + (ax)^{2^{t+1}}), where a ∈ 𝔽_{2}^{m}.

Problem 1. Let τ be a trilinear alternate form. We have a natural map from E into Λ^{2}(E) which sends a ∈ E on a bilinear form. Let r(a) be the rank of the image of a. What can we say about ∑_{a∈E} 2^{r(a)} when τ varies ?

Problem 2. Let f be a boolean function. From proposition 1, we know that f decomposes as ∑_{S∈X} 1_{S} where X is a set of affine subspaces. Let x and y be two vectors of E. The derivation of f in the direction of {x, y} is D_{x,y}(f) = ∑_{S∈X} d(x, y, S)1_{S(x,y)} where S(x, y) is the affine space S ∪ (x + S) ∪ (y + S) ∪ (x + y + S), and where d(x, y, S) ∈ 𝔽_{2} is equal to 0 if and only if the direction of S contains al least one vector of x, y or x + y. Use this description to construct a set X of variety of codimension 3 in order to obtain a cubic with small kernel.

7. Numerical Results

The next tables give all the values of kernel, and default for all the cubic functions, 4 ≤ m ≤ 7. Kernels and defaults are affine invariant, so we use the action of the general linear group GL(m, 𝔽_{2}) on the space of boolean cubics modulo the space of quadratic functions to reduce the problem of enumeration. In the paper [8], one can find systems of representatives for small m. For each representative h, there is a three columns table. Let us denote by k be the cardinality of the kernel of h. When q ranges the space of the homogeneous quadratic functions ker(h + q) is invariant, the value of k appears in the header of the table. A row (d, δ, c) means that there are c homogeneous quadratic functions q with d defaults, and δ is to k − 2d : the quantity that appears in the RHS of (12). Note that if f is a boolean

KERNELS AND DEFAULTS 7

function of degree more than 2 then its kernel and default do not depend of the affine terms.

m = 4, k = 88, h_{1} m = 4, k = 88, h_{2}
24 40 56 24 40 56
0 88  8 24 40 56
m = 5, k = 352, h_{1} m = 5, k = 184, h_{3}
132  88 512 60  64 192
144  64 336 48  88 480
96 160 168 36 112 320
0 352 8 0 184 32
m = 6, k = 1408, h_{1}  m = 6, k = 736, h_{3}
528 352 3584 336 64 192
624  160 25088 288 160 23520
672  64  1344  96 544  32
576  256  2352 240 256  8192
384  640  392 192 352  480
0 1408  8 144 448  320
0 736  32
m = 6, k = 316, h_{6}  m = 6, k = 484, h_{4}  m = 6, k = 400, h_{5}
84 148  7680 168 148 10752 168  64  64
60 196 21504 144 196 18816 120 160 15680
36 244  3584  96 292  3136  96 208 14336
0 484  64  72 256  2240
24 352  448
m = 7, k = 5632, h_{1}  m = 7, k = 760, h_{12}
2640 352 917504 240 280 32256
2112 1408  17920 216 328 516096
2496  640 376320 192 376 959616
2688  256 772800 168 424 368640
2304 1024  11760  0 760  128
1536 2560  840  96 568  16128
0 5632  8 144 472 204288
m = 7, k = 2944, h_{3}  m = 7, k = 928, h_{10}
1104  736  32768 168 592  6144
1248  448 512000 216 496  92160
1296  352 983040 312 304 284672
1344  256 450624 264 400 632832
1152 640 93600 336 256 3072
384 2176  96 288 352 801792
960 1024  24192 240 448 236288
768 1408  480 192 544  27648
576 1792  320 144 640  11776
0 2944  32  48 832  768

m = 7, k = 1936, h_{4}  m = 7, k = 1600, h_{5}  m = 7, k = 1264, h_{8}
768  400 903168 672  256  161344 456  352 589824
672  592 111104 624  352 1376256 480  304 483840
816  304 903168 576  448  397824 384  496 225408
720  496 150528 480  640  26432 336  592  46080
576  784  18816 528  544  114688 288  688  18944
528  880  7168 384  832  17920 144  976  1024
384 1168  3136 288 1024  2240 192  880  768
0 1936  64  96 1408  448  0 1264  128
432  400 731136
m = 7, k = 2272, h_{7}  m = 7, k = 1264, h_{6}  m = 7, k = 928, h_{9}
1008  256 368640 480 304  645120 336 256  24576
960  352 999936 336 592  7680 288 352 1476608
912  448 645120 432 400 1290240 240 448  544768
768  736  40320 384 496  129024 144 640  28672
720  832  43008 240 784  21504 192 544  21504
0 2272  128 144 976  3584  0 928  1024
m = 7, k = 592, h_{11}
120 352  983040
96 400 1024000
48 496  81920
0 592  8192

List of homogeneous cubics : h_{1} = X_{1}X_{2}X_{3}, h_{2} = X_{1}X_{2}X_{3} + X_{2}X_{3}X_{4}, h_{3} = X_{1}X_{2}X_{3} + X_{2}X_{4}X_{5}, h_{4} = X_{1}X_{2}X_{3} + X_{4}X_{5}X_{6}, h_{5} = X_{1}X_{2}X_{3} + X_{2}X_{4}X_{5} + X_{3}X_{4}X_{6}, h_{6} = X_{1}X_{2}X_{3} + X_{1}X_{4}X_{5} + X_{2}X_{4}X_{6} + X_{3}X_{5}X_{6} + X_{4}X_{5}X_{6}, h_{7} = X_{1}X_{2}X_{7} + X_{3}X_{4}X_{7} + X_{5}X_{6}X_{7}, h_{8} = X_{1}X_{2}X_{3} + X_{4}X_{5}X_{6} + X_{1}X_{4}X_{7}, h_{9} = X_{1}X_{2}X_{3} + X_{2}X_{4}X_{5} + X_{3}X_{4}X_{6} + X_{1}X_{4}X_{7}, h_{10} = X_{1}X_{2}X_{3} + X_{4}X_{5}X_{6} + X_{1}X_{4}X_{7} + X_{2}X_{5}X_{7}, h_{11} = X_{1}X_{2}X_{3} + X_{1}X_{4}X_{5} + X_{2}X_{4}X_{6} + X_{3}X_{5}X_{6} + X_{4}X_{5}X_{6} + X_{1}X_{6}X_{7}, h_{12} = X_{1}X_{2}X_{3} + X_{1}X_{4}X_{5} + X_{2}X_{4}X_{6} + X_{3}X_{5}X_{6} + X_{4}X_{5}X_{6} + X_{2}X_{4}X_{7} + X_{1}X_{6}X_{7} .

References

[1] C. Carlet. A new generalization of bent functions to the odd case. private communication.

[2] C. Carlet. Codes de Reed-Muller, codes de Kerdock et de Preparata. 1990.

[3] P. Delsarte. A geometrical approach to a class of cyclic codes. Journal of Combinatorial Theory, 6, 1969.

[4] P. Delsarte and J.M. Goethals. Alternating bilinear forms over gf(q). Journal of combinatorial theory, (A) 19, 1975.

[5] J. Dieudonné. La géométrie des groupes classiques. 1971.

[6] J. F. Dillon. Elementary Hadamard Difference Sets. 1974.

[7] J.M. Goethals. Nonlinear codes and quadratic forms. Information and Control, 31(1), [8] X.D. Hou. gl(m, 2) acting on r(r, m)/r(r − 1, m).

[9] X.D. Hou. On the covering radius of (1, m) into (3, m).

[10] Ph. Langevin. The covering radius of RM(1, 9) in RM(3, 9), volume 514. 1990.

[11] Ph. Langevin. rayon de recouvrement des codes de Reed-Muller affines. 1992.

[12] J. J. Mykkelveit. The covering radius of the (128,8) reed-muller codes is 56. IEEE transactions on information theory, 26, 1980.

[13] N.J. Patterson and D.H. Wiedemann D.H. The covering radius of the (2^{15}, 16) reedmuller code is at least 16276.

[14] O.S. Rothaus. on bent functions. Journal of Combinatorial Theory, 20, 1976.

[15] Harold N. Ward. Combinatorial polarization. Discrete Math., 26, 1979.

CNRS, I3S, bâtiment 4, 250 rue A. Einstein, 06560 Valbonne, France

   E-mail address: langevin@alto.unice.fr, sole@alto.unice.fr