1 Introduction

Side-channel analysis is a very powerful technique which target implementations of block ciphers [12, 13, 16, 17]. To resist side channel attacks, many possible countermeasures have been proposed, and correlation-immune (CI) Boolean functions with low Hamming weights can be used in the framework [6, 14, 15, 20]. To reduce the cost overhead of countermeasures, one needs to construct d-CI functions with the weight as small as possible, or maximizing d for a given weight [2, 6].

Very recently, Carlet and Chen proposed some constructions of low-weight CI functions, and conjectured that the minimum Hamming weight of 3-CI functions in n variables is \(8\lceil \frac{n}{4}\rceil \) [5].

In this paper, we study minimum Hamming weights of 3-CI Boolean functions, and prove that the Carlet-Chen conjecture is equivalent to the famous Hadamard conjecture. Moreover, we propose a method to construct low-weight n-variable CI functions through d-linearly independent sets, which can provide numerous minimum-weight d-CI functions. Particularly, we obtain some new values of the minimum Hamming weights of d-CI functions in n variables for \(n\le 13\).

The paper is organized as follows. In Sect. 2, the necessary background is established. We then study the relationship between Hadamard matrices and minimum-weight d-CI functions in Sect. 3. In Sect. 4, we study the relationship between d-linearly independent sets and low-weight d-CI functions. We end in Sect. 5 with conclusions.

2 Preliminaries

Let \({\mathbb {F}}_{2}^{n}\) be the n-dimensional vector space over the finite field \({\mathbb {F}}_{2}\). We denote by \({\mathcal {B}}_{n}\) the set of all n-variable Boolean functions, from \({\mathbb {F}}_{2}^{n}\) into \({\mathbb {F}}_{2}\).

Any Boolean function \(f\in {\mathcal {B}}_{n}\) can be represented by its truth table

$$\begin{aligned}{}[f(0,0,\ldots ,0),f(1,0,\ldots ,0),f(0,1,\ldots ,0),f(1,1,\ldots ,0),\ldots ,f(1,1,\ldots ,1)]. \end{aligned}$$

Let \({\mathbf {a}}=(a_1,\ldots ,a_n)\in {\mathbb {F}}_{2}^{n}\). The Hamming weight of \({\mathbf {a}}\), denoted by \(w_H({\mathbf {a}})\), is the cardinality of the set \(\{1\le i\le n | a_i=1\}\).

Let \(Supp(f)=\{{\mathbf {x}}\in {\mathbb {F}}_{2}^{n}|f({\mathbf {x}})=1\}\) be the support of a Boolean function \(f\in B_n\), whose cardinality |Supp(f)| is called the Hamming weight of f, and will be denoted by \(w_H(f)\). Clearly, f is determined by Supp(f) uniquely. We say that f is balanced if \(w_H(f)=2^{n-1}\).

Let \(f\in {\mathcal {B}}_{n}\). f is called correlation-immune of order d (in brief, d-CI) if and only if

$$\begin{aligned} \sum _{{\mathbf {x}}\in {\mathbb {F}}_{2}^{n}}(-1)^{f({\mathbf {x}})\oplus {\mathbf {v}}\cdot {\mathbf {x}}}=0, \end{aligned}$$

for any \({\mathbf {v}}=(v_1,\ldots ,v_n)\in {\mathbb {F}}_{2}^{n}\) satisfying \(1\le w_H({\mathbf {v}})\le d\), where \({\mathbf {v}}\cdot {\mathbf {x}}=v_1x_1+\cdots +v_nx_n\) is the usual inner product [4, 7, 19, 22].

Clearly, for \({\mathbf {0}}\ne {\mathbf {v}}\in {\mathbb {F}}_{2}^{n}\), we have

$$\begin{aligned} \sum _{{\mathbf {x}}\in {\mathbb {F}}_{2}^{n}}(-1)^{f({\mathbf {x}})\oplus {\mathbf {v}}\cdot {\mathbf {x}}}=\sum _{{\mathbf {x}}\in Supp(f)}(-1)^{1\oplus {\mathbf {v}}\cdot {\mathbf {x}}}+ \sum _{{\mathbf {x}}\notin Supp(f)}(-1)^{{\mathbf {v}}\cdot {\mathbf {x}}}=-2\sum _{{\mathbf {x}}\in Supp(f)}(-1)^{{\mathbf {v}}\cdot {\mathbf {x}}}. \end{aligned}$$

Therefore, f is d-CI if and only if

$$\begin{aligned} \sum _{{\mathbf {x}}\in Supp(f)}(-1)^{{\mathbf {v}}\cdot {\mathbf {x}}}=0, \end{aligned}$$

for any \({\mathbf {v}}\in {\mathbb {F}}_{2}^{n}\) satisfying \(1\le w_H({\mathbf {v}})\le d\).

A matrix H of order n is called a Hadamard matrix if \(HH^T=nI_n\), where \(I_n\) is the \(n\times n\) identity matrix and \(H^T\) is the transpose of H [10].

3 Hadamard matrices and minimum Hamming weights of d-CI Boolean functions

3.1 On the minimum weight of 3-CI Boolean functions

Using the same notation as that of [5], we denote the minimum Hamming weight of d-CI nonzero Boolean functions in n variables as \(w_{n,d}\).

Lemma 3.1

(Proposition 2.6 of [5]) Let d be an even integer such that \(n\ge d\ge 2\). Then \(w_{n+1,d+1}=2w_{n,d}\).

Theorem 3.2

Let \(n\ge 3\) be any integer. Then \(w_{n,3}\ge 8\lceil \frac{n}{4}\rceil \).

Proof

By Lemma 3.1, it is sufficient to prove that \(w_{n,2}\ge 4\lceil \frac{n+1}{4}\rceil \), for \(n\ge 2\). Suppose there is an \(n\ge 2\) such that \(m=w_{n,2}<4\lceil \frac{n+1}{4}\rceil \). Then there exists a 2-CI \(f\in {\mathcal {B}}_n\) with the Hamming weight m. It is well known that \(\deg (f)\le n-2\) and m is a multiple of 4. Therefore, \(m\le 4\lceil \frac{n+1}{4}\rceil -4<n+1\). Let the support of f be \(\{(a_{i1},a_{i2},\ldots ,a_{in})\}\), where \(1\le i\le m\). Let M be the matrix

$$\begin{aligned} M=\left[ \begin{array} {ccccc} a_{11} &{}\quad a_{12} &{}\quad \cdots &{}\quad a_{1n} \\ a_{21} &{}\quad a_{22}&{}\quad \cdots &{}\quad a_{2n} \\ \cdots &{}\quad \cdots &{}\quad \cdots &{}\quad \cdots \\ a_{m1}&{} \quad a_{m2} &{}\quad \cdots &{}\quad a_{mn} \end{array} \right] =[{\mathbf {p}}_1,\ldots ,{\mathbf {p}}_n], \end{aligned}$$

where \({\mathbf {p}}_{j}=(a_{1j},a_{2j},\ldots ,a_{mj})^T\) and \(1\le j\le n\). Since f is 2-CI, we have \(w_H({\mathbf {p}}_{j})=\frac{m}{2}\) and \(w_H({\mathbf {p}}_{j_1}\oplus {\mathbf {p}}_{j_2})=\frac{m}{2}\), where \(1\le j\le n\) and \(1\le j_1<j_2\le n\). Therefore,

$$\begin{aligned} {\mathbf {p}}_{i_1}^T {\mathbf {p}}_{i_2}=\left\{ \begin{array} {l} \frac{m}{2} \ \ \ if \ i_1=i_2,\\ \frac{m}{4} \ \ \ otherwise. \end{array} \right. \end{aligned}$$

We construct an \(m\times (n+1)\) matrix H as follows.

$$\begin{aligned} H=\left[ \begin{array} {cccccc} 1&{}\quad (-1)^{a_{11}} &{}\quad (-1)^{a_{12}} &{}\quad \cdots &{}\quad (-1)^{a_{1n}} \\ 1&{}\quad (-1)^{a_{21}} &{}\quad (-1)^{a_{22}}&{}\quad \cdots &{} \quad (-1)^{a_{2n}} \\ \cdots &{}\quad \cdots &{}\quad \cdots &{}\quad \cdots \\ 1&{}\quad (-1)^{a_{m1}}&{}\quad (-1)^{a_{m2}} &{}\quad \cdots &{}\quad (-1)^{a_{mn}} \end{array} \right] . \end{aligned}$$

Then

$$\begin{aligned} H^TH=mI, \end{aligned}$$

where I is the identity \((n+1)\times (n+1)\) matrix. Therefore,

$$\begin{aligned} n+1=rank(H^TH)\le rank(H)\le m<n+1, \end{aligned}$$

which is a contradiction, and the result follows. \(\square \)

By Theorem 3.2, if we can find a 2-CI n-variable Boolean function with the weight \(4\lceil \frac{n+1}{4}\rceil \), then the values of \(w_{n,2}\) and \(w_{n+1,3}\) are both determined. We now give a method to construct minimum-weight 2-CI n-variable functions through Hadamard matrices, for infinitely many n’s.

Construction 1

Let H be any \(4k\times 4k\) Hadamard matrix. By negating columns of H, we can get a matrix whose first row is \((1,1,\dots ,1)\). We delete this row and denote the induced \((4k-1)\times 4k\) matrix as

$$\begin{aligned}{\widetilde{H}}= \left[ \begin{array} {ccccc} (-1)^{a_{1,1}} &{} (-1)^{a_{1,2}} &{} \cdots &{} (-1)^{a_{1,4k}} \\ (-1)^{a_{2,1}} &{} (-1)^{a_{2,2}}&{} \cdots &{} (-1)^{a_{2,4k}} \\ \cdots &{}\cdots &{}\cdots \\ (-1)^{a_{4k-1,1}}&{} (-1)^{a_{4k-1,2}} &{} \cdots &{} (-1)^{a_{4k-1,4k}} \end{array} \right] , \end{aligned}$$

where \(a_{i,j}\in {\mathbb {F}}_{2}\), \(1\le i\le 4k-1\) and \(1\le j\le 4k\). Let \({\mathbf {q}}_j=(a_{1,j},\ldots ,a_{4k-1,j})\), where \(1\le j\le 4k\). Then we construct a function \(f\in {\mathcal {B}}_{4k-1}\) whose support is \(\{{\mathbf {q}}_1,{\mathbf {q}}_2,\ldots ,{\mathbf {q}}_{4k}\}\).

Proposition 3.3

Let H be any \(4k\times 4k\) Hadamard matrix, and \(f\in {\mathcal {B}}_{4k-1}\) be the function defined in Construction 1. Then f is a 2-CI Boolean function with the minimum Hamming weight.

Proof

Since H is a Hadamard matrix, the rows of the induced matrix \({\widetilde{H}}=[(-1)^{a_{i,j}}]\) in Construction 1 are mutually orthogonal and they are all orthogonal to the vector \((1,1,\ldots ,1)\). Let \({\mathbf {p}}_{i}=(a_{i,1},a_{i,2},\ldots ,a_{i,4k})\), where \(1\le i\le 4k-1\). Then \(w_H({\mathbf {p}}_{i})=2k\) and \(w_H({\mathbf {p}}_{i_1}\oplus {\mathbf {p}}_{i_2})=2k\), where \(1\le i\le 4k-1\) and \(1\le i_1<i_2\le 4k-1\). Therefore, f is 2-CI. Since \(w_H(f)=4k=4\lceil \frac{4k-1+1}{4}\rceil \), by Theorem 3.2, f is a 2-CI Boolean function with the minimum Hamming weight. \(\square \)

It is noted that we can construct a 3-CI n-variable Boolean function with the minimum Hamming weight easily from a 2-CI \((n-1)\)-variable Boolean function with the minimum Hamming weight.

Corollary 3.4

If there exists a Hadamard matrix H of order 4k, then \(w_{4k,3}=8k\).

In [2], Bhasin et al. presented an open problem: the minimal weight of a d-CI function in n variables might not increase with n. By Corollary 3.4, we can give a negative answer to this problem, since there are infinitely many Hadamard matrices.

3.2 Equivalence of the Hadamard and Carlet–Chen conjectures

Hadamard conjectured that there exists a Hadamard matrix of order 4k for every positive integer k. After more than one hundred years, this conjecture still remains open.

Conjecture 3.5

(Hadamard Conjecture) A Hadamard matrix of order 4k exists for every positive integer k.

There are many results on this conjecture (see e.g. [1, 8, 9, 11, 18, 21]). The smallest order for which no Hadamard matrix has been known is 668.

In [5], based on the numerical results, Carlet and Chen proposed the following conjecture.

Conjecture 3.6

(Carlet-Chen Conjecture) Let \(n\ge 3\) be any integer. Then \(w_{n,3}=8\lceil \frac{n}{4}\rceil \).

We now prove that the above two conjectures are equivalent.

Theorem 3.7

The Carlet-Chen conjecture is equivalent to the Hadamard conjecture.

Proof

If the Carlet-Chen conjecture holds, then for any positive integer k, we have \(w_{4k,3}=8k\). Hence, \(w_{4k-1,2}=4k\). That is, there exists a 2-CI \(f\in {\mathcal {B}}_{4k-1}\) with the Hamming weight 4k. Let the support of f be \(\{(a_{i,1},a_{i,2},\ldots ,a_{i,4k-1})\}\), where \(1\le i\le 4k\). We construct a \(4k\times 4k\) matrix H as follows.

$$\begin{aligned} H=\left[ \begin{array} {cccccc} 1&{}\quad (-1)^{a_{1,1}} &{}\quad (-1)^{a_{1,2}} &{}\quad \cdots &{}\quad (-1)^{a_{1,4k-1}} \\ 1&{}\quad (-1)^{a_{2,1}} &{}\quad (-1)^{a_{2,2}}&{}\quad \cdots &{}\quad (-1)^{a_{2,4k-1}} \\ \cdots &{}\quad \cdots &{}\quad \cdots &{}\quad \cdots \\ 1&{}\quad (-1)^{a_{4k,1}}&{}\quad (-1)^{a_{4k,2}} &{}\quad \cdots &{} \quad (-1)^{a_{4k,4k-1}} \end{array} \right] . \end{aligned}$$

Then \(H^TH=4kI\), where I is the identity \(4k\times 4k\) matrix. That is, \(H^T\) is a Hadamard matrix of order 4k.

Now suppose the Hadamard conjecture is correct. Then for any positive integer k, there exists a Hadamard matrix H of order 4k. By Proposition 3.3, the function defined in Construction 1 is a 2-CI Boolean function with the Hamming weight 4k. Therefore, \(w_{4k-1,2}\le 4k\). By Lemma 3.1 and Theorem 3.2, we have \(w_{4k,3}=8k\). For \(1\le t\le 3\), we have \(w_{4k+t,3}\le w_{4k+4,3}=8(k+1)\). Then by Theorem 3.2, \(8(k+1)\ge w_{4k+t,3}\ge 8\lceil \frac{4k+t}{4}\rceil =8(k+1)\), and the result follows. \(\square \)

From the proof of Theorem 3.7, for any minimum-weight 2-CI function \(f\in {\mathcal {B}}_{4k-1}\), there always exists a Hadamard matrix of order 4k such that the function defined in Construction 1 is the same as f. In other words, our construction can provide all minimum-weight 2-CI Boolean functions in \(4k-1\) variables.

4 d-linearly independent sets and d-CI Boolean functions with low Hamming weights

4.1 d-Linearly independent sets

We now introduce the notion, d-linearly independent set, which will be used in our construction of d-CI Boolean functions with low Hamming weights.

Definition 4.1

A subset of \({\mathbb {F}}_{2}^{m}\) is said to be d-linearly independent if no vector in the set can be written as a linear combination of any other \(d-1\) vectors in the set. That is, for any different vectors \(\alpha _1,\alpha _2,\ldots ,\alpha _d\) of this set, there do not exist \(c_1,\ldots ,c_d\in {\mathbb {F}}_{2}\) such that \(\sum _{i=1}^dc_i\alpha _i=0\).

Definition 4.2

A subset S of \({\mathbb {F}}_{2}^{m}\) with k vectors is said to be a relative maximum d-linearly independent set if S is not a subset of any d-linearly independent set of \({\mathbb {F}}_{2}^{m}\) with \(k+1\) vectors.

Clearly, any d-linearly independent set can be extended to a relative maximum d-linearly independent set, and the rank of a relative maximum d-linearly independent set is m.

Definition 4.3

A subset of \({\mathbb {F}}_{2}^{m}\) with k vectors is said to be an absolute maximum d-linearly independent set if there is no d-linearly independent set of \({\mathbb {F}}_{2}^{m}\) with \(k+1\) vectors. We denote this maximum value k as \(v_{m,d}\).

It is easy to see that \(v_{m,2}=2^m-1\) and \(v_{m,d_1}\ge v_{m,d_2}\) for \(d_1<d_2\). We now determine other values of \(v_{m,d}\).

Proposition 4.4

The cardinality of an absolute maximum 3-linearly independent set of \({\mathbb {F}}_{2}^{m}\) is \(2^{m-1}\). That is, \(v_{m,3}=2^{m-1}\).

Proof

Suppose there exists a 3-linearly independent set \(\{{\mathbf {p}}_1,{\mathbf {p}}_2,\ldots ,{\mathbf {p}}_{2^{m-1}+1}\}\subset {\mathbb {F}}_{2}^{m}\). Then we construct a set

$$\begin{aligned} T=\{{\mathbf {p}}_i, \ 1\le i\le 2^{m-1}+1\}\bigcup \{{\mathbf {p}}_1+{\mathbf {p}}_j, \ 2\le j\le 2^{m-1}+1\}. \end{aligned}$$

Clearly, the cardinality of the set T is \(2^{m-1}+1+2^{m-1}> 2^m\), which is contradictory to the fact that T is a subset of \({\mathbb {F}}_{2}^{m}\). Therefore, \(v_{m,3}\le 2^{m-1}\). Clearly, the set

$$\begin{aligned} S=\{{\mathbf {p}}\in {\mathbb {F}}_{2}^{m}| w_H({\mathbf {p}}) \ is \ odd \} \end{aligned}$$

is a 3-linearly independent set with \(2^{m-1}\) vectors, and the result follows. \(\square \)

Proposition 4.5

For \(m\ge 5\) and \(d\ge \frac{2m+2}{3}\), the cardinality of an absolute maximum d-linearly independent set of \({\mathbb {F}}_{2}^{m}\) is \(m+1\). That is, \(v_{m,d}=m+1\), for \(d\ge \frac{2m+2}{3}\).

Proof

Let \(S=\{{\mathbf {p}}_1,{\mathbf {p}}_2,\ldots ,{\mathbf {p}}_{t}\}\subset {\mathbb {F}}_{2}^{m}\) be any absolute maximum d-linearly independent set. Take a basis of S, say \(\{{\mathbf {p}}_1,{\mathbf {p}}_2,\ldots ,{\mathbf {p}}_{m}\}\). Then any vector in S can be written as a linear combination of the basis vectors. We have

$$\begin{aligned} \left[ \begin{array} {cc} {\mathbf {p}}_1 \\ {\mathbf {p}}_2 \\ \ldots \\ {\mathbf {p}}_m\\ {\mathbf {p}}_{m+1} \\ \ldots \\ {\mathbf {p}}_t \end{array} \right] =\left[ \begin{array} {ccccc} 1 &{} 0 &{} \ldots &{} 0 \\ 0 &{} 1 &{} \ldots &{} 0 \\ \ldots &{} \ldots &{}\ldots &{} \ldots \\ 0 &{} 0 &{} \ldots &{} 1 \\ c_{m+1,1} &{} c_{m+1,2} &{} \ldots &{} c_{m+1,m}\\ \ldots &{} \ldots &{}\ldots &{} \ldots \\ c_{t,1} &{} c_{t,2} &{} \ldots &{} c_{t,m} \end{array} \right] \left[ \begin{array} {cc} {\mathbf {p}}_1 \\ {\mathbf {p}}_2 \\ \ldots \\ {\mathbf {p}}_m \end{array} \right] , \end{aligned}$$

where \((c_{i,1}, c_{i,2}, \ldots , c_{i,m})\in {\mathbb {F}}_{2}^{m}\), for \(m+1\le i\le t\). Therefore,

$$\begin{aligned} T=\{(1,0,\ldots ,0),\ldots , (0,0,\ldots ,1),(c_{m+1,1}, \ldots , c_{m+1,m}),\ldots , (c_{t,1}, \ldots , c_{t,m})\} \end{aligned}$$

is an absolute maximum d-linearly independent set. Since \(d\ge \frac{2m+2}{3}\), there is no vector \({\mathbf {q}} \in T\) with \(1<w_H({\mathbf {q}})< \frac{2m+2}{3}\). Moreover, there do not exist two different vectors \({\mathbf {q}}_1,{\mathbf {q}}_2\in T\) such that \(w_H({\mathbf {q}}_1)\ge \frac{2m+2}{3}\) and \(w_H({\mathbf {q}}_2)\ge \frac{2m+2}{3}\). Otherwise, \({\mathbf {q}}_1\oplus {\mathbf {q}}_2\) is of the Hamming weight

$$\begin{aligned} \le \frac{2m-4}{3}=\frac{2m+2}{3}-2 \end{aligned}$$

and it can be written as a linear combination of other \(\frac{2m+2}{3}-2\) vectors in T. Therefore, the cardinality of T is at most \(m+1\). Clearly, the set

$$\begin{aligned} S=\{{\mathbf {p}}\in {\mathbb {F}}_{2}^{m} |w_H({\mathbf {p}})=1 \ or \ m\} \end{aligned}$$

is a d-linearly independent set with \(m+1\) vectors, and the result follows. \(\square \)

If m is small, it is quite easy to determine the values of \(v_{m,d}\). In Table 1, we list all the values of \(v_{m,d}\), for \(m\le 9\).

Table 1 The values of \(v_{m,d}\)
Full size table

4.2 An algorithm for finding relative maximum d-linearly independent sets

Let \(S\subset {\mathbb {F}}_{2}^{m}\) be any relative maximum d-linearly independent set. Then S is of rank m, and there is a linear transformation over \({\mathbb {F}}_{2}^{m}\) which maps S onto a set T containing m unit vectors. Clearly, T is also a relative maximum d-linearly independent set. Moreover, the inverse transformation maps T onto S. Hence, without loss of generality, we only need to study how to find relative maximum d-linearly independent sets from the set of unit vectors \(U=\{{\mathbf {u}}_1,\ldots ,{\mathbf {u}}_{m}\}\), where \({\mathbf {u}}_i\) is the unit vector whose i-th coordinate is 1, for \(1\le i\le m\).

Let \({\mathbf {u}}=(u_1,u_2,\ldots ,u_m)\in {\mathbb {F}}_{2}^{m}\). We use \(|{\mathbf {u}}|\) to denote the number \(u_1+2u_2+\ldots +2^{m-1}u_m\), and provide an algorithm as follows.

An algorithm for finding relative maximumd-linearly independent sets:

  1. 1.

    Start with the set of unit vectors \(U=\{{\mathbf {u}}_1,\ldots ,{\mathbf {u}}_{m}\}\) and \(i=d\).

  2. 2.

    Consider \({\mathbf {u}}\in {\mathbb {F}}_{2}^{m}\) satisfying \(wt({\mathbf {u}})=i\) which are sorted by \(|{\mathbf {u}}|\) in ascending size.

    1. a.

      If \({\mathbf {u}}\) cannot be written as a linear combination of \(d-1\) vectors in U, update U to \(U\cup \{{\mathbf {u}}\}\);

    2. b.

      If \(|{\mathbf {u}}|=2^{m}-2^{m-i}\), update i to \(i+1\).

    3. c.

      If \(i>m\), goto step 3.

  3. 3.

    Output the set U.

In the algorithm, we sort \({\mathbf {u}}\) with the same weight by \(|{\mathbf {u}}|\) in ascending size, and the last \({\mathbf {u}}\) satisfying \(wt({\mathbf {u}})=i\) is \((0,\ldots ,0,1,\ldots ,1)\) with \(|{\mathbf {u}}|=2^{m}-2^{m-i}\). The algorithm is simple and even can be done by hand, which can be seen from the following example.

Example 1

Let \(m=7\) and \(d=4\). Then the set of unit vectors is

$$\begin{aligned} U=&\{(1, 0, 0, 0, 0, 0, 0),(0, 1, 0, 0, 0, 0, 0),(0, 0, 1, 0, 0, 0, 0),(0, 0, 0, 1, 0, 0, 0),\\&(0, 0, 0, 0, 1, 0, 0),(0, 0, 0, 0, 0, 1, 0),(0, 0, 0, 0, 0, 0, 1)\}. \end{aligned}$$

Consider vectors of weight 4. We can find the following four vectors one by one:

$$\begin{aligned} (1, 1, 1, 1, 0, 0, 0),(1, 1, 0, 0, 1, 1, 0),(1, 0, 1, 0, 1, 0, 1),(0,0,0,1,1,1,1), \end{aligned}$$

and U is updated to the set with eleven vectors. Clearly, any vector of weight greater than 4 can be written as a linear combination of three vectors in U. Therefore, a relative maximum 4-linearly independent set with 11 vectors has been found (it is in fact an absolute maximum 4-linearly independent set).

Remark 1

It seems that the above algorithm always generates an absolute maximum d-linearly independent set, but we cannot prove it, which we leave as an open problem.

4.3 Constructing d-CI Boolean functions with low weights through relative maximum d-linearly independent sets

We now give a method to construct low-weight d-CI n-variable functions through relative maximum d-linearly independent sets (a similar method was used in Sect. V of [3]).

Construction 2

Let \(S=\{{\mathbf {u}}_1,\ldots ,{\mathbf {u}}_{k}\}\subset {\mathbb {F}}_{2}^{m}\) be a relative maximum d-linearly independent set. Let \(l_j\in {\mathcal {B}}_m\) be the linear function \({\mathbf {u}}_j \cdot {\mathbf {x}}\), where \({\mathbf {x}}\in {\mathbb {F}}_{2}^{m}\) and “\(\cdot \)” is the usual inner product. The truth table of \(l_j\) is denoted by the column vector \({\mathbf {p}}_j=(a_{1,j},a_{2,j},\ldots ,a_{2^m,j})^T\). Let

$$\begin{aligned} M=[\mathbf {{\mathbf {p}}_1},\ldots ,{\mathbf {p}}_{k}]=\left[ \begin{array} {ccccc} a_{1,1} &{} a_{1,2} &{} \cdots &{} a_{1,k} \\ a_{2,1} &{} a_{2,2}&{} \cdots &{} a_{2,k} \\ \cdots &{} \cdots &{}\cdots &{}\cdots \\ a_{2^m,1}&{} a_{2^m,2} &{} \cdots &{} a_{2^m,k} \end{array} \right] =\left[ \begin{array} {c} {\mathbf {q}}_1 \\ {\mathbf {q}}_2 \\ \cdots \\ {\mathbf {q}}_{2^m} \end{array} \right] , \end{aligned}$$

where \({\mathbf {q}}_i\in {\mathbb {F}}_2^{k}\) and \(1\le i\le 2^m\). Then we construct a function \(f\in {\mathcal {B}}_{k}\) whose support is \(\{{\mathbf {q}}_1,{\mathbf {q}}_2,\ldots ,{\mathbf {q}}_{2^m}\}\).

We give an example to illustrate the construction.

Example 2

Take \(m=10\) and \(d=6\). Using the above algorithm, we can generate the following relative maximum 6-linearly independent set by hand quite easily.

$$\begin{aligned} S=&\{(1, 0, 0, 0, 0, 0, 0,0, 0, 0),(0, 1, 0,0, 0, 0, 0, 0, 0, 0),(0, 0, 1, 0, 0,0, 0, 0, 0, 0),\\&(0, 0, 0, 1, 0,0, 0, 0, 0, 0),(0, 0, 0, 0, 1, 0, 0,0, 0, 0),(0, 0, 0, 0, 0, 1, 0,0, 0, 0),\\&(0, 0, 0, 0, 0, 0, 1, 0,0, 0),(0, 0, 0, 0, 0, 0, 0, 1, 0,0),(0, 0, 0, 0, 0, 0, 0, 0, 1,0),\\&(0, 0, 0, 0, 0, 0, 0, 0, 0,1),(1, 1, 1, 1, 1,1,0, 0,0, 0),(1, 1, 1, 0, 0, 0, 1, 1, 1,0),\\&(1, 0, 0, 1, 1, 0, 1, 1,0, 1)\}. \end{aligned}$$

In fact, S is an absolute maximum 6-linearly independent set. We have

$$\begin{aligned}&l_1=x_1, \ l_2=x_2, \ l_3=x_3, \ l_4=x_4, \ l_5=x_5, \ l_6=x_6, \ l_7=x_7, \ l_8=x_8 \\&\ l_9=x_9, l_{10}=x_{10}, \ l_{11}=x_1\oplus x_2\oplus x_3\oplus x_4\oplus x_5\oplus x_6,\\&l_{12}=x_1\oplus x_2\oplus x_3\oplus x_7\oplus x_8\oplus x_9, \ l_{13}= x_1\oplus x_4\oplus x_5\oplus x_7\oplus x_8\oplus x_{10}. \end{aligned}$$

Then we can get the function \(f\in {\mathcal {B}}_{13}\) by Construction 2 with the support

$$\begin{aligned}&\{(0, 0, 0, 0, 0, 0, 0, 0, 0,0,0, 0, 0),(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,1,1),\\&(0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1,1,0),(1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,0,1), \\&\ldots ,(0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1,1),(1, 1, 1, 1, 1, 1, 1, 1,1,1, 0, 0, 0)\} \end{aligned}$$

It is easy to check that f is a 6-CI Boolean function with the Hamming weight 1024. Therefore, \(w_{13,6}\le 1024\). Since \(w_{13,6}\ge 1024\) (the lower bound was obtained by the Delsarte LP algorithm, see TABLE I of [5]), we have \(w_{13,6}=1024\). This is a previously unknown value, thus a triple question mark ??? in Table II of [5] can be taken place by it.

Table 2 The values of \(w_{n,d}\)
Full size table

Proposition 4.6

Let \(f\in {\mathcal {B}}_{k}\) be the function defined in Construction 2. Then f is a d-CI Boolean function with the Hamming weight \(2^m\).

Proof

Since S is a relative maximum d-linearly independent set, it is of rank m and \({\mathbf {q}}_1,{\mathbf {q}}_2,\ldots ,{\mathbf {q}}_{2^m}\) are different vectors. Therefore, f is a well-defined Boolean function with the Hamming weight \(2^m\). Clearly, f is d-CI if and only if

$$\begin{aligned} \sum _{{\mathbf {x}}\in Supp(f)}(-1)^{{\mathbf {v}}\cdot {\mathbf {x}}}=0, \end{aligned}$$

for any \({\mathbf {v}}=(v_1,\ldots ,v_k)\in {\mathbb {F}}_2^{k}\) satisfying \(1\le w_H({\mathbf {v}})\le d\). That is, \(w_H(v_1\mathbf {p_1}\oplus \ldots \oplus v_k\mathbf {p_k})=2^{m-1}\), for any \({\mathbf {v}}\in {\mathbb {F}}_2^{k}\) with \(1\le w_H({\mathbf {v}})\le d\). Since S is d-linearly independent, for any \({\mathbf {v}}\in {\mathbb {F}}_2^{k}\) with \(1\le w_H({\mathbf {v}})\le d\), we have \(v_1{\mathbf {u}}_1+\ldots +v_k{\mathbf {u}}_k\ne {\mathbf {0}}\). Therefore,

$$\begin{aligned} v_1l_1\oplus \ldots \oplus v_kl_k=(v_1{\mathbf {u}}_1+\ldots +v_k{\mathbf {u}}_k)\cdot {\mathbf {x}} \end{aligned}$$

is a balanced function, and the result follows. \(\square \)

Theorem 4.7

Let \(v_{m,d}\) be the cardinality of the absolute maximum d-linearly independent set of \({\mathbb {F}}_{2}^{m}\). Then

$$\begin{aligned} w_{v_{m,d},d}\le 2^m. \end{aligned}$$

Proof

Let \(S=\{{\mathbf {u}}_1,\ldots ,{\mathbf {u}}_{k}\}\subset {\mathbb {F}}_{2}^{m}\) be an absolute maximum d-linearly independent set. Then \(k=v_{m,d}\). By Construction 2, we can generate a function \(f\in {\mathcal {B}}_{v_{m,d}}\). By Proposition 4.6, f is a d-CI Boolean function with the Hamming weight \(2^m\). Therefore,

$$\begin{aligned} w_{v_{m,d},d}\le 2^m. \end{aligned}$$

For \(n\le 13\), there are 8 unknown values of \(w_{n,d}\) (see Table II of [5]). By Theorem 4.7 and Table 1, we can determine the exact values for three of them. That is, \(w_{11,4}=128\), \(w_{12,5}=256\) and \(w_{13,6}=1024\). For other unknown values, Theorem 4.7 provides an upper bound. In Table 2, we list the values of \(w_{n,d}\) for \(n\le 13\). All values for \(n\le 10\) can be determined by the SMT tool [2], and those entries in italic are new values obtained by [2, 5]. Those entries in bold are new values obtained by us.

The number of rows of an orthogonal array can be lower bounded by the Delsarte LP bound, and the bounds were given in Table 1 of [2]. In Appendix 1, we deduce exact values for some orthogonal arrays and give some results on the maximum number of orthogonal vectors in \({\mathbb {F}}_{2}^{n}\). Based on the result of Appendix 1 and Theorem 4.7, we have \(w_{11,4}=128\). Then in Appendix 1, we give an 11-variable 4-CI Boolean function with the minimum Hamming weight.\(\square \)

5 Conclusion

In this paper, we studied the relationships between Hadamard matrices, d-linearly independent sets and correlation-immune Boolean functions with minimum Hamming weights. The field is still open and there are many problems deserved to be studied. We hope that our work would attract more researchers to be interested in this interesting topic.