The Maximum Nonlinearity of 8-variable Balanced Boolean Functions is 116

The Maximum Nonlinearity of 8-variable Balanced Boolean Functions is 116

arXiv:2610.17897v1 [cs.IT] 13 Oct 2026

Yueying Lou∗, Youle Xu† and Qichun Wang ‡§

Abstract Does there exist an 8-variable balanced Boolean function with nonlinearity 118? This is a famous and long-standing open problem in Boolean functions. In this paper, we give a negative answer to this open problem, and prove that the maximum nonlinearity of balanced Boolean functions in 8 variables is 116, establishing the 8-variable instance of Dobbertin’s conjectured recursion for the minimum Walsh peak of balanced functions. Equivalently, the covering radius of the Reed–Muller code RM(1,8) in 0-resilient Boolean functions is 116. We deduce the result by obtaining a quadratic form of polar rank 6, and reducing the problem to the existence of a 6-variable Boolean function with nonlinearity greater than 26 whose Hamming distance to a bent function is between 4 and 6.

Keywords: Boolean functions, nonlinearity, Walsh transform, quadratic forms, polar rank, bent functions, Reed–Muller codes.

1

Introduction

Boolean functions are fundamental objects in cryptography and coding theory [2, 14]. An n-variable Boolean function is a map from the n-dimensional vector space Fn2 to the binary field F2 . To be used in the design of symmetric ciphers, Boolean functions should be balanced and with high nonlinearity ∗

School of Computer and Electronic Information/School of Artificial Intelligence,Nanjing Normal University, Nanjing, China. Email: 232212001@njnu.edu.cn. † China Telecom Corporation Limited, Huaibei Branch, China. Email: youlexu@163.com. ‡ School of Computer and Electronic Information/School of Artificial Intelligence, Nanjing Normal University, Nanjing, China. Email: qcwang@fudan.edu.cn. § Corresponding author.

1

[6]. A 2n-variable bent function has the maximum nonlinearity 22n−1 −2n−1 . However, it is not balanced. The upper bound for the nonlinearity of 2nvariable balanced Boolean functions is 22n−1 − 2n−1 − 2, which is tight for n ≤ 3. It is an open problem whether this bound is always tight. In particular, does there exist an 8-variable balanced Boolean function with nonlinearity 118? This is a famous and long-standing open problem in Boolean functions (see e.g., [2, 3, 7, 16, 18]). Let N LBn be the maximum nonlinearity of n-variable balanced Boolean functions. It has been conjectured by Dobbertin [8] that N LB2n = 22n−1 − 2n + N LBn , which is still unsettled for n ≥ 4 [17]. Particularly, if the conjecture is true, then the minimum Walsh peak of 8-variable balanced Boolean functions should be 24, and N LB8 = 116. The r-th order Reed–Muller code of length 2m , denoted by RM(r, m), is the binary linear code formed by truth tables of all m-variable Boolean functions of algebraic degree ≤ r. The covering radius of RM(1, m) is the maximum nonlinearity of m-variable Boolean functions, which is known for m even or m < 9. There are 9-variable unbalanced Boolean functions with nonlinearity 242 in the generalized rotation symmetric class [12, 13], thus the covering radius of RM(1,9) is at least 242. For odd m > 9, the covering radius of RM(1, m) is completely open. To resist fast correlation attacks and linear attacks, Boolean functions used in stream ciphers should be t-resilient and with high nonlinearity. So, covering radius of Reed–Muller codes for t-resilient functions was defined [1, 10], and the covering radius of RM(1,8) in 0-resilient Boolean functions is the same as N LB8 . In this paper, we give a negative answer to that famous open problem, and prove that N LB8 = 116, establishing the 8-variable instance of Dobbertin’s conjectured recursion for the minimum Walsh peak of balanced functions. Equivalently, the covering radius of the Reed–Muller code RM(1,8) in 0-resilient Boolean functions is 116. The rest of the paper is organized as follows. In Section 2, the necessary background is established. In Section 3, we deduce the result by obtaining a quadratic form of polar rank 6, and reducing the problem to the existence of a 6-variable Boolean function with nonlinearity greater than 26 whose Hamming distance to a bent function is between 4 and 6. We end in Section 4 with conclusion and open problems.

2

2

Preliminaries

Let F2 denote the binary finite field, and let Fn2 be the n-dimensional vector space over F2 . A Boolean function of n variables is a map from Fn2 to F2 . We denote by Bn the set of all n-variable Boolean functions. Every Boolean function has a unique algebraic normal form (ANF), which is its multivariate polynomial representation over F2 : Y f (x1 , . . . , xn ) = ⊕S⊆{1,2,...,n} aS xi . i∈S

The algebraic degree of f , denoted by deg(f ), equals max{|S| : aS ̸= 0}. The function f is affine, if deg(f ) ≤ 1. We use An to denote the set of all n-variable affine functions. That is, An = {g ∈ Bn : deg(g) ≤ 1}. Let f ∈ Bn and supp(f ) = {x ∈ Fn2 : f (x) = 1}. The cardinality |supp(f )| is called the Hamming weight of f , and will be denoted by wt(f ). The function f is balanced if wt(f ) = 2n−1 . Let f, g ∈ Bn . The Hamming distance between f and g is d(f, g) = wt(f ⊕ g). The nonlinearity of f , denoted by nl(f ), is the minimum distance between f and the set of affine functions. That is, nl(f ) = ming∈An d(f, g). The Reed–Muller code RM(r, m) is the set of truth-tables of all mvariable Boolean functions whose algebraic degree is at most r. The covering radius of RM (r, n) is defined as max d(f, RM (r, n)) = max min d(f, g).

f ∈Bn

f ∈Bn deg(g)≤r

For more information on the covering radius, we refer to [9, 21]. It is known that RM(r, m) has minimum Hamming distance 2m−r . That is, the weight of an m-variable Boolean function of degree r is at least 2m−r [11, 15] The Walsh transform of a given function f ∈ Bn is the integer-valued function over Fn2 defined by X Wf (ω) = (−1)f (x)+ω·x , x∈Fn 2

where ω ∈ Fn2 , and ω · x = ω1 x1 + · · · + ωn xn is the usual inner product. It is easy to see that a Boolean function f is balanced if and only if Wf (0) = 0. If Wf (ω) = 0 for any ω ∈ Fn2 satisfying 0 ≤ wt(ω) ≤ t, then f is called t-resilient [20, 22]. 3

The nonlinearity of f can be determined by nl(f ) = 2n−1 −

1 max |Wf (ω)|. 2 ω∈F2n

By the Parseval formulae, maxω |Wf (ω)| ≥ 2n/2 . Therefore, n

nl(f ) ≤ 2n−1 − 2 2 −1 . If the upper bound is achieved, then f is a bent function. Clearly, bent function only exists for n even, and its algebraic degree is at most n2 [4, 5, 19]. For a real function f on F2n , the Fourier-Hadamard transform of f is the integer-valued function over Fn2 defined by X Hn f (ω) = f (x)(−1)ω·x . x∈Fn 2

Writing (f1 , f2 ) =

P

x f1 (x)f2 (x), character orthogonality gives

Hn2 = 2n I,

X

(Hn f )(ω)2 = 2n

ω∈F2n

X

f (ω)2 ,

ω∈F2n

and (Hn f1 , f2 ) = (f1 , Hn f2 ) [2]. Let f1 , f2 ∈ Bn . We use || to denote the concatenation, that is, (f1 ||f2 )(x1 , . . . , xn , xn+1 ) = (xn+1 ⊕ 1)f1 (x1 , . . . , xn ) ⊕ xn+1 f2 (x1 , . . . , xn ).

3

The maximum nonlinearity of 8-variable balanced Boolean functions is 116

We use N LB8 to denote the maximum nonlinearity of an 8-variable balanced Boolean function. Assume that N LB8 = 118. Then there exists a balanced f ∈ B8 with |Wf (ω)| ≤ 20 for any ω ∈ F28 . If ω ̸= 0, then we have Wf (ω) = −256 + 4|x ∈ supp(f ) : ω · x = 1|.

(1)

Let b = ⊕x∈supp(f ) x. Then X

|x ∈ supp(f ) : ω · x = 1| =

ω · x ≡ ω · b (mod 2).

x∈supp(f )

Therefore, Wf (ω) ≡ 4ω · b (mod 8). If b = 0, then Wf (ω) is a multiple of 8 and |Wf (ω)| ≤ 16. That is, f is a bent function, which is contradictory to 4

the fact that f is balanced. Hence b ̸= 0. Choose an invertible matrix M with M e8 = b and replace f (x) by f (M x), where e8 = (0, ..., 0, 1). Then the support sum becomes e8 and the set of the Walsh spectrum stays the same. In the following, we take this new function as f , and we have b = ⊕x∈supp(f ) x = e8 .

3.1

A congruence connecting the Walsh spectrum and the quadratic form

In this subsection, we will deduce a congruence connecting the Walsh spectrum and the quadratic form. Lemma 1. Let t ∈ F2n . Then ⊕ni=1 ti ≡

n X i=1

1− ⊕ni=1 ti = n Y

Qn

i=1 (1 − 2ti )

2 X

(1 − 2ti ) = 1 +

i=1

ti tj (mod 4).

1≤i<j≤n

Proof. Clearly,

Since

X

ti + 2

.

(−2)|I|

Y

ti ,

i∈I

∅̸=I⊆{1,...,n}

we have X

⊕ni=1 ti =

(−2)|I|−1

Y

ti ,

i∈I

∅̸=I⊆{1,...,n}

and the result follows. Proposition 1. If N LB8 = 118, then there exists a balanced g ∈ B8 of nonlinearity 118 satisfying ⊕x∈supp(g) x = e8 and Wg (a, c) ≡ 4c + 8Q(a) (mod 16),

(2)

for any (a, c) ∈ F27 × F2 , where Q(a) ∈ B7 is a quadratic function with Q(0) = 0. P Proof. For the function f defined as above, let Xi = x∈supp(f ) xi and P 8 Xij = x∈supp(f ) xi xj . By Lemma 1, for any ω, x ∈ F2 , we have ω · x = ⊕8i=1 ωi xi ≡

8 X

ωi x i + 2

i=1

X 1≤i<j≤8

5

ωi xi ωj xj (mod 4).

Summing over supp(f ) and using (1), we have Wf (ω) ≡ 4

8 X

X

Xi ωi + 8

i=1

Xij ωi ωj (mod 16).

1≤i<j≤8

Since the support sum is e8 , there exist integers Di such that Xi = ei8 +2Di , where ei8 ∈ F2 and it equals one only when i = 8. Define the quadratic function Q0 (ω) =

8 X

(Di mod 2)ωi +

i=1

X

(Xij mod 2)ωi ωj .

1≤i<j≤8

Then Q0 (0) = 0 and Wf (a, c) ≡ 4c + 8Q0 (a, c) (mod 16). Since 8Q0 ≡ 8(Q0 (mod 2)) (mod 16), Q0 can be viewed as a Boolean function. Write Q0 (a, c) = Q(a) ⊕ c(a · s ⊕ t), where s ∈ F27 , t ∈ F2 and Q ∈ B7 . Clearly, s and t stay the same for any (a, c), and Q(0) = 0. Let d = (s, t) and g(x) = f (x ⊕ d). Then g ∈ B8 preserves the set P of the Walsh coefficients and the support sum b (since P x = x∈supp(f ) x + 128d ≡ b (mod 2)). Clearly, x∈supp(g) Wg (a, c) = (−1)(a,c)·d Wf (a, c) = (−1)a·s+ct Wf (a, c). If c = 0, then Wg (a, c) = ±Wf (a, c) ≡ 8Q(a) (mod 16). If c = 1 and a · s + t = 0, then Wg (a, c) = Wf (a, c) ≡ 4 + 8Q(a) (mod 16). If c = 1 and a · s + t = 1, then Wg (a, c) = −Wf (a, c) ≡ −4 + 8(Q(a) + 1) ≡ 4 + 8Q(a) (mod 16), and the result follows. By Proposition 1, we have the following Table 1 on the distribution of Wg (a, c), where a ∈ F27 and c ∈ F2 . 6

Table 1: Distribution of Wg (a, c) Q(a) 0 1

Wg (a, 0) -16, 0, 16 -8, 8

Wg (a, 1) -12, 4, 20 -20, -4, 12

In the following, we use hi , 0 ≤ i ≤ 5 to denote the number of Walsh coefficients of absolute value 4i. Table 1 shows that all zero coefficients occur in Wg (a, 0), all coefficients of magnitude 4 occur in Wg (a, 1), and exactly wt(Q) positions have magnitude 8 in Wg (a, 0). In particular, h2 = wt(Q) and h0 ≥ 1. Assume that N LB8 = 118. Then we obtain a quadratic form Q (here quadratic forms may include linear terms). We will investigate Q further and deduce a contradiction.

3.2

The polar rank of the quadratic form Q must be 6

For a quadratic Boolean function f with f (0) = 0, its polar form is Bf (x, y) = f (x + y) + f (x) + f (y). Its radical is the set of y with Bf (x, y) = 0 for all x. The polar rank means the rank of Bf , and nondegenerate means that its radical is zero. It is known that the polar rank must be even [2]. In this section, we will prove that the polar rank of Q must be 6. Lemma 2 (Proposition 55 of [2]). Let f ∈ Bn be quadratic with f (0) = 0 and polar rank 2r. Then |Wf (ω)| is supported on an affine subspace of size 22r , and all its nonzero values have magnitude 2n−r . Therefore, wt(f ) ∈ {2n−1 , 2n−1 − 2n−r−1 , 2n−1 + 2n−r−1 }. If r = 0, then wt(f ) ∈ {0, 2n−1 }. Write g = g0 ||g1 , where g0 , g1 ∈ B7 . Let u(y) =

(−1)g0 (y) + (−1)g1 (y) (−1)g0 (y) − (−1)g1 (y) , v(y) = . 2 2

Then u, v ∈ {0, ±1}, u2 + v 2 = 1, uv = 0, and Wg (a, 0) = 2H7 u(a), Wg (a, 1) = 2H7 v(a).

(3)

Lemma 3. We have (Wg (a, 1), (−1)Q(a) ) = 256 + 32(h0 + h1 ) + 24wt(Q). 7

(4)

Proof. By Table 1, we have X Wg (a, 0)2 = 0 · h0 + 64wt(Q) + 256(128 − h0 − wt(Q)) a∈F27

= 32768 − 256h0 − 192wt(Q). Then by the Parseval formulae, we have X Wg (a, 1)2 = 32768 + 256h0 + 192wt(Q).

(5)

a∈F27

By Table 1, |Wg (a, 1) − 4(−1)Q(a) | ∈ {0, 16}, and it equals 0 if and only if |Wg (a, 1)| = 4. Therefore, X (Wg (a, 1) − 4(−1)Q(a) )2 = 256(128 − h1 ). a∈F27

Then by (5), we have 256h0 + 192wt(Q) − 8(Wg (a, 1), (−1)Q (a)) + 2048 = −256h1 , and the result follows. Proposition 2. The polar rank of Q is 6. Proof. Let the polar rank of Q be 2r. By (3), we have (Wg (a, 1), (−1)Q(a) ) = 2(H7 v, (−1)Q ) = 2(v, H7 (−1)Q ). Then by Lemma 2, (Wg (a, 1), (−1)Q(a) ) ≤ 2

X

|(H7 (−1)Q )(y)| = 2 · 22r · 27−r = 28+r .

y

Therefore, by Lemma 3, we have 256 + 32(h0 + h1 ) + 24wt(Q) ≤ 28+r .

(6)

If r = 0, then 256 + 32h0 ≤ 256, which is contradictory to h0 ≥ 1. If r = 1, by Lemma 2, wt(Q) ≥ 32. Then by (6), we have 256 + 24 · 32 ≤ 512, which is a contradiction. If r = 2, then by Lemma 2 and (6), we have wt(Q) ≥ 48 and 256 + 24 · 48 ≤ 1024, again a contradiction. Therefore, r = 3, and the result follows. 8

By Proposition 2, the polar rank of Q must be 6. Then by Lemma 2, wt(Q) ∈ {56, 64, 72}. Moreover, by (6), 3 h0 + h1 ≤ 56 − wt(Q). 4

(7)

Since 32768−256h0 −192wt(Q) =

X

Wg (a, 0)2 = 4

a∈F27

X

(H7 u)(a)2 = 4·128|supp(u)|,

a∈F27

we have

h0 3wt(Q) − . (8) 2 8 Since |supp(u)| is an integer and h0 ≥ 1, we have h0 ≥ 2 must be even. |supp(u)| = 64 −

3.3

wt(Q) must be 56

We now split the seven-dimensional space as F26 × F2 . Since the polar rank of Q is 6, its radical has dimension 1. Choose its nonzero vector r0 as the last vector of a basis. Then F27 = V0 ⊕ < r0 >, where V0 is a sixdimensional complement of the radical. Clearly, for any a ∈ F26 , we have BQ ((a, 0), (0, 1)) = 0. Let p(a) = Q(a, 0) and λ = Q(0, 1). Then Q(a, j) = Q((a, 0) + j(0, 1)) = Q(a, 0) + Q(j(0, 1)) + BQ ((a, 0), j(0, 1)) = p(a) + λj. Here p is the restriction to V0 , and p(0) = 0. Its polar form is nondegenerate: a vector in V0 orthogonal to all of V0 is also orthogonal to the radical, hence to the whole space. It belongs to both V0 and the radical, so is zero. By Lemma 2, p ∈ B6 is a bent function. Let ϵ = H6 ((−1)p )/8. Then ϵ ∈ {±1} and H6 ϵ = 8(−1)p . Moreover,  X 16ϵ(y), t = λ Q p j(λ+t) (H7 (−1) )(y, t) = (H6 (−1) )(y) (−1) = 0, t ̸= λ. j∈F2

Write L = {(y, λ) : y ∈ F26 } and R = F27 \ L. Both halves are identified with F26 by the coordinate y. In particular, vL (y) = v(y, λ) and vR (y) = v(y, 1 + λ); the restrictions uL and uR are defined in the same way.

9

In the following, we will deduce that vL (y) = ±1 and the associated 6variable Boolean function is of nonlinearity greater than 26 whose Hamming distance to a bent function is between 4 and 6. On L, let z count the positions with vL = 0 and let w count those with vL = −ϵ. Then (vL , ϵ) = −w + (64 − z − w) = 64 − z − 2w. Furthermore, (Wg (a, 1), (−1)Q(a) ) = 2(v, H7 (−1)Q ) = 32(vL , ϵ) = 32(64 − z − 2w). Then by (4), we have 3 z + 2w = 56 − h0 − h1 − wt(Q). 4

(9)

On R, we have |supp(vR )| = |supp(v)| − |supp(vL )| = (128 − |supp(u)|) − (64 − z). Then by (8), we have |supp(vR )| =

h0 3wt(Q) + + z. 2 8

(10)

Lemma 4. Let z and w be defined as above. Then 3 |supp(vR )| ≤ 4 + z + 5w. 2

(11)

Proof. Clearly, for any (a, j) ∈ F27 , we have H7 v(a, j) = (−1)jλ (H6 vL (a) + (−1)j H6 vR (a)). Since |2H7 v| = |Wg (a, 1)| ≤ 20, we have |H6 vL (a)| + |H6 vR (a)| ≤ 10. Furhtermore, X X |H6 vL (a)| ≥ (−1)p(a) H6 vL (a) = 8(ϵ, vL ) = 8(64 − z − 2w). a

(12)

(13)

a

By the Parseval formulae, we have X X (H6 vL (a))2 = 64(64 − z), (H6 vR (a))2 = 64|supp(vR )|. a

a

10

(14)

Therefore, by (12), (13) and (14), we have X X (10 − |(H6 vL (a)|)2 (H6 vR (a))2 ≤ 64|supp(vR )| = a

a

≤ 6400 − 160(64 − z − 2w) + 64(64 − z) = 256 + 160(z + 2w) − 64z, and the result follows. Proposition 3. We have wt(Q) = 56. Proof. By Lemma 2, wt(Q) ∈ {56, 64, 72}. If wt(Q) = 72, then by (7), h0 +h1 ≤ 2. Therefore, h0 = 2 and h1 = 0. Thus (9) and (10) give z+2w = 0 and |supp(vR )| = 28 + z. Therefore, z = w = 0 and |supp(vR )| = 28, which is contradictory to (11). If wt(Q) = 64, then by (9) and h0 ≥ 2, we have z + 2w = 56 − h0 − h1 − 48 ≤ 6. Then by Lemma 4, |supp(vR )| ≤ 4 + 52 (z + w) − z ≤ 19 − z. Furthermore, by (10), h0 |supp(vR )| = + 24 + z ≥ 25 + z. 2 Therefore, 19 − z ≥ |supp(vR )| ≥ 25 + z, which is a contradiction, and the result follows. Since Q(a, j) = p(a) + λj, if λ = 1, then Q(a, 0) and Q(a, 1) contains exactly one value equal to one, giving wt(Q) = 64. Therefore, λ = 0 and wt(p) = wt(Q)/2 = 28. In this remaining case, by (9) and (10), we have z + 2w = 14 − h0 − h1 ≤ 12, |supp(vR )| = 21 +

3.4

h0 + z ≥ 22 + z. 2

(15)

|vL | = 1

Since u2 + v 2 = 0, supp(uL ) = z. Set A(ω) = Wg (ω, 0), where ω ∈ F27 . By (3), A = 2H7 u. Therefore, for a ∈ F26 , we have A(a, 0) A(a, 1) = H6 uL (a) + H6 uR (a), = H6 uL (a) − H6 uR (a). 2 2 Their sum is 2H6 uL (a). By (2) and Q(a, j) = p(a), A(a, 0) A(a, 1) ≡ ≡ 4p(a) (mod 8). 2 2 11

Therefore, 2H6 uL (a) ≡ 8p(a) ≡ 0 (mod 8) and H6 uL (a) ≡ 0 (mod 4).

(16)

Lemma 5. If z ∈ {4, 6}, then |{a ∈ F26 : p(a) = 0, H6 uL (a) = ±4}| ≥ 6. Proof. Since p is a bent function and Wp (0) = 8, we have X X (H6 uL (a))2 (H6 uL (a))2 − p(a)=1

p(a)=0

=

X

=

X

(−1)p(a) (H6 uL (a))2

a

uL (x)uL (y)

X (−1)p(a)+a·(x+y) a

x,y

X

=

Wp (0) +

x=y∈supp(uL )

X

uL (x)uL (y)Wp (x + y)

x̸=y∈supp(uL )

≥ 8z − 8z(z − 1)) = 16z − 8z 2 . Moreover, by the Parseval formulae, we have X X (H6 uL (a))2 + (H6 uL (a))2 = 64z. p(a)=0

p(a)=1

Therefore, 2

X

(H6 uL (a))2 ≥ 16z − 8z 2 + 64z = 192.

p(a)=0

Since (16) and |H6 uL (a)| ≤ z ≤ 6, we have H6 uL (a) ∈ {0, ±4}. Hence, |{a ∈ F26 : p(a) = 0, H6 uL (a) = ±4}| ≥ 192 ÷ 2 ÷ 16 = 6.

Proposition 4. z must be zero. Proof. Clearly, H6 uL (a) =

X

uL (−1)a·x ≡ |supp(uL )| = z (mod 2).

x∈supp(uL )

Then by (16), z is even. If z = 2, let supp(uL ) = {x1 , x2 }. Choose a such that (−1)a·(x1 +x2 ) = uL (x1 )uL (x2 ). Then uL (x1 )(−1)a·x1 = uL (x2 )(−1)a·x2 , 12

and |H6 uL (a)| = 2, which is contradictory to (16). If z ≥ 8, then by (11) and (15), we have 5 5 |supp(vR )| ≤ 4 + (z + 2w) − z ≤ 4 + × 12 − z ≤ 26, 2 2 and |supp(vR )| ≥ 22 + 8 = 30, which is a contradiction. Let S = {a ∈ F26 : p(a) = 0, H6 uL (a) = ±4}. If z ∈ {4, 6}, by Lemma 5, |S| ≥ 6. If a ∈ S, then Q(a) = p(a) = 0. Hence, by Table 1, {A(a, 0), A(a, 1) : a ∈ F26 } = {Wg (ω, 0) : ω ∈ F27 } ⊆ {0, ±16}. Furthermore, A(a, 0) A(a, 1) + = 2H6 uL (a) = ±8. 2 2 Therefore, exactly one of A(a, 0) and A(a, 1) is zero. Hence, h0 ≥ |S| ≥ 6. By (15), we have |supp(vR )| = 21 +

h0 + z ≥ 24 + z. 2

However, by (11) and (15), we have 5 5 |supp(vR )| ≤ 4 + (z + 2w) − z = 4 + (14 − h0 − h1 ) − z ≤ 24 − z. 2 2 This is a contradiction, and the result follows. By Proposition 4, we have |vL | = 1.

3.5

Completion of the proof

Lemma 6. Let f1 , f2 ∈ B6 , where f1 is a bent function. If d(f1 , f2 ) ∈ {4, 5, 6}, then nl(f2 ) ≤ 26. Proof. Let h = f1 ⊕ f2 . Then wt(h) ∈ {4, 5, 6}. Since the minimum Hamming distance of RM (3, 6) is 26−3 = 8, we have deg(h) ≥ 4. Hence, deg(f2 ) = deg(f1 ⊕ h) ≥ 4. So, f2 is not a bent function and nl(f2 ) < 28. If wt(h) ∈ {4, 6}, then nl(f2 ) is even, and nl(f2 ) ≤ 26. If wt(h) = 5, let Wf1 (x) = 8(−1)f0 (x) , where f0 ∈ B6 is the dual bent function. For each x ∈ supp(h), define a Boolean function of ω ∈ F26 : ϕx (ω) = f0 (ω) ⊕ f1 (x) ⊕ ω · x. 13

Then wt(ϕx ) = 28. Thus, for each fixed x ∈ supp(h), there are exactly 28 values of ω with ϕx (ω) = 1. Now take x ̸= y ∈ supp(h). We have ϕx (ω) ⊕ ϕy (ω) = f1 (x) ⊕ f1 (y) ⊕ ω · (x ⊕ y), which is a nonconstant affine function of ω. So it is 1 for exactly 32 values of ω. Let N (ω) = |{x ∈ supp(h) : ϕx (ω) = 1}|. Therefore, X

N (ω) = 5 × 28 = 140,

ω

and

X N (ω) ω

2

  5 = × 32 = 320. 2

Since

  3 × 64 = 192 < 320, 2 there exists some ω0 such that N (ω0 ) ≥ 4. Choose l(x) = ω0 · x ⊕ f0 (ω0 ). Then d(f2 , l) = d(f1 ⊕ h, l) = wt(ϕx (ω0 ) ⊕ h) ≤ 28 − 4 + 1 = 25, and the result follows. Since ϵ = H6 ((−1)p )/8, we have |ϵ| = 1 and H6 ϵ = 8(−1)p . Let ϵ = (−1)f1 , where f1 ∈ B6 . Then |Wf1 (ω)| = 8, and f1 is a bent function. We now can complete the proof. Theorem 1. The maximum nonlinearity of 8-variable balanced Boolean functions is 116. Proof. Assume N LB8 = 118. Then according to the above discussion, |vL | = 1 and by (9), vL is obtained from ϵ by changing 1 1 w = (56 − h0 − h1 − 42) ≤ (56 − 2 − 42) = 6 2 2 signs. Furthermore, by (11) and (15), we have 22 ≤ |supp(vR )| ≤ 4 + 5w. Hence, w ≥ 4. That is, w ∈ {4, 5, 6}. Let vL = (−1)f2 , where f2 ∈ B6 . Then d(f1 , f2 ) ∈ {4, 5, 6}. Moreover, by (12), we have |Wf2 (a)| ≤ 10, for any a ∈ F26 . Therefore, nl(f2 ) ≥ 27, which is contradictory to Lemma 6, and the result follows. 14

4

Conclusion and open problems

In this paper, we proved that the maximum nonlinearity of balanced Boolean functions in 8 variables is 116. A similar analysis for ≥ 10 variables may deduce more interesting results. We leave this for future work. Finally, we list some related open problems that could be further considered. Open problem 1. Does there exist a 9-variable balanced Boolean function with nonlinearity 242? Open problem 2. Determine the covering radius of RM(1,9). Open problem 3. Does there exist a 10-variable balanced Boolean function with nonlinearity 494? Open problem 4. Let f ∈ B2n be balanced. Do we have nl(f ) ≤ 22n−1 − 2n−1 − 4 for any n ≥ 4?

Acknowledgment The authors would like to thank the financial support from the National Natural Science Foundation of China (Grant 62172230). We also thank the anonymous reviewers, whose comments helped improving the paper.

References [1] Y. L. Borissov, A. Braeken, S. Nikova and B. Preneel, “On the covering radii of binary Reed-Muller codes in the set of resilient Boolean functions, ” IEEE Transactions on Information Theory, 51:3 (2005), 1182–1189. [2] C. Carlet, “Boolean Functions for Cryptography and Coding Theory,” Cambridge University Press, 2021. [3] C. Carlet, M. Djurasevic, D. Jakobovic, L. Mariot and S. Picek, “Evolving constructions for balanced, highly nonlinear boolean functions,” GECCO, 2022, pp. 1147–1155. [4] C. Carlet, M. Djurasevic, D. Jakobovic, L. Mariot, S. Picek and A. Polujan, “On Counts and Densities of Homogeneous Bent Functions: An Evolutionary Approach,” EvoApplications, 2026, pp. 216–232.

15

[5] C. Carlet and S. Mesnager, “Four decades of research on bent functions,” Designs, Codes and Cryptography, 78:1 (2016), 5–50. [6] T. W. Cusick and P. Stanica, “Cryptographic Boolean Functions and Applications,” Academic Press, 2017. [7] M. Djurasevic, D. Jakobovic, L. Mariot and S. Picek, “A survey of metaheuristic algorithms for the design of cryptographic Boolean functions,” Cryptography and Communications, 15 (2023), 1171–1197. [8] H. Dobbertin, “Construction of bent functions and balanced Boolean functions with high nonlinearity,” Fast Software Encryption, 1995, pp. 61–74. [9] J. Gao, H. Kan, Y. Li and Q. Wang, “The Covering Radius of the Third-Order Reed-Muller Code RM(3,7) is 20, ” IEEE Transactions on Information Theory, 69:6 (2023), 3663–3671. [10] T. Iwata, T. Yoshiwara, and K. Kurosawa,“New Covering Radius of Reed–Muller Codes for t-Resilient Functions,” Selected Areas in Cryptography, 2001, pp. 75–86. [11] T. Kasami and N. Tokura, “On the weight structure of the Reed–Muller codes, ” IEEE Transactions on Information Theory, 16 (1970), 752–759. [12] S. Kavut and M. D. Yücel, “9-variable boolean functions with nonlinearity 242 in the generalized rotation symmetric class, ” Information and Computation, 208:4 (2010), 341–350. [13] S. Kavut, S. Maitra and M. D. Yücel, “Search for boolean functions with excellent profiles in the rotation symmetric class, ” IEEE Transactions on Information Theory, 53:5 (2007), 1743–1751. [14] O. A. Logachev, A. A. Salnikov and V. V. Yashchenko, “Boolean Functions in Coding Theory and Cryptography,” American Mathematical Society, 2012. [15] F. J. MacWilliams and N. J. Sloane, “The theory of error-correcting codes, ” North Holland, 1977. [16] S. Maitra, B. Mandal and M. Roy,“Modifying Bent Functions to Obtain the Balanced Ones with High Nonlinearity,” Progress in Cryptology – INDOCRYPT, 2023, pp. 449–470.

16

[17] E. özçekiç, S. Kavut and H. Kutucu , “Genetic Approach to Improve Cryptographic Properties of Balanced Boolean Functions Using Bent Functions, ” Computers, 12:8 (2023), Art. no. 129. [18] S. Picek, R. Santana and D. Jakobovic,“Maximal nonlinearity in balanced boolean functions with even number of inputs, revisited,” 2016 IEEE Congress on Evolutionary Computation, 2016, pp. 3222–3229. [19] O. S. Rothaus, “On bent functions,” Journal of Combinatorial Theory, Series A, 20:3 (1976), 300–305. [20] L. Sun, Z. Shi and J. Liu, “Some constructions of rotation symmetric Boolean functions with high order resiliency,” Discrete Mathematics, 349 (2026), Art. no. 115123. [21] Q. Wang, “The covering radius of the Reed–Muller code RM(2,7) is 40,” Discrete Mathematics, 342 (2019), Art. no. 111625. [22] G. Z. Xiao and J. L. Massey, “A spectral characterization of correlationimmune combining functions,” IEEE Transactions on Information Theory, 34:3 (1988), 569–571.

17

Related documents

• The Maximum Nonlinearity of 8-variable Balanced Boolean Functions is 116#1343096
• Further results on the relation between nonlinearity and resiliency of Boolean functions#340226
• Explicit Constructions of Maximum-Cardinality Families of Plateaued Functions with Pairwise Disjoint Walsh Supports#1035793
• Maximizing $p$-Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types#1200068
• Introspectively Envy-Free and Efficient Allocation of Indivisible Mixed Manna#1355542