Constructions of 2-Correlation Immune Rotation Symmetric Boolean Functions

Jiao DU, Ziwei ZHAO, Shaojing FU, Longjiang QU, Chao LI

Summary :

In this paper, we first recall the concept of 2-tuples distribution matrix, and further study its properties. Based on these properties, we find four special classes of 2-tuples distribution matrices. Then, we provide a new sufficient and necessary condition for n-variable rotation symmetric Boolean functions to be 2-correlation immune. Finally, we give a new method for constructing such functions when n=4t - 1 is prime, and we show an illustrative example.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.8 pp.1241-1246
• Publication Date: 2024/08/01
• Publicized: 2024/03/22
• Online ISSN: 1745-1337
• DOI: 10.1587/transfun.2023EAP1144
• Type of Manuscript: PAPER
• Category: Cryptography and Information Security

1.  Introduction

Boolean functions are used for designing stream ciphers, block ciphers and hash functions in cryptography. Their cryptographic properties greatly influence cryptosystem security. Rotation symmetric Boolean functions (RSBFs) are a special class of Boolean functions, which are invariant under circular translation of indices. RSBFs were introduced by Filiol and Fontaine in [1], [2] under the name of idempotent functions and studied by Pieprzyk and Qu [3] under their final name. The fact that the special structure of RSBFs allows for faster computation makes it possible to quickly search for Boolean functions with good cryptographic properties. For instance, nonlinearity and correlation immunity of RSBFs were studied in [4], [5].

A Boolean function \(f\) is said to be correlation immune of order \(d\) (in brief, \(d\)-correlation immune or \(d\)-CI) if the output distribution of \(f\) does not change when at most \(d\) input variables are fixed [6]. In 1988, Xiao and Massey [7] gave a characterization of \(d\)-CI Boolean functions by use of the Fourier-Hadamand transform. Since then, the correlation immune Boolean function has been an active area of research, and correlation immunity has been one of the main design criteria for shift registers based on stream ciphers [8], [9]. In addition, the correlation immune functions are closely related to orthogonal arrays, which was introduced by C.R. Rao [10].

In terms of the counting and constructions of correlation immune RSBFs, St\(\breve{\mathrm{a}}\)nic\(\breve{\mathrm{a}}\) P. [4] first gave the enumerative results of \(1\)-CI RSBFs when \(n\) is prime. Fu et al. [11] studied the number of \(1\)-CI RSBFs, and gave the exact number of \(1\)-CI RSBFs with \(11\) variables. The resilient functions is a special class of correlation immune functions. Some elaborate sufficient and necessary conditions for the existence of 1- and 2-RSBFs in a given number of variables are given in [12]. In 2020, Du et al. [13] proposed the concept of \(2\)-tuples distribution matrix of the rotation symmetric orbits, and then constructed a class of 2-resilient RSBFs with \(4t-1\) variables. Recently, Du et al. [14] proposed a new characterization of \(2\)-resilient RSBFs by the \(2\)-tuples distribution matrix. So far as we know, there are few results about \(2\)-CI RSBFs. We will study the constructions of 2-CI RSBFs based on the results proposed in [4].

In this work, we first further study the properties of the \(2\)-tuples distribution matrix, and give four special classes of \(2\)-tuples distribution matrices. Based on these results, a new sufficient and necessary condition of \(2\)-correlation immune RSBFs is proposed. At last, we give a new method to construct such functions with \(n\) variables, where \(n=4t-1\) is prime, and an example is given to illustrate the method.

The rest of the paper is organized as follows. In Sect. 2, we recall some necessary notions and definitions. In Sect. 3, we introduce the properties of the \(2\)-tuples distribution matrix. In Sect. 4, we propose a new sufficient and necessary condition of \(2\)-correlation immune RSBFs, and a concrete constructions of \(2\)-correlation immune RSBFs are demonstrated. Moreover, an illustrative examples are given. Finally, Sect. 5 concludes the article.

2.  Preliminaries

Let \({\mathbb F}_{2}^{n}\) be the \(n\)-dimensional vector space over the binary finite field, i.e., \({\mathbb F}_{2}=\{0,1\}\). An \(n\)-variable Boolean function is a mapping from \({\mathbb F}_{2}^{n}\) to \({\mathbb F}_{2}\). Define \(\textbf{B}_{n}\) to be the set of all \(n\)-variable Boolean functions. The support of \(f\in \textbf{B}_{n}\) is defined as \(supp(f)=\{\boldsymbol{x}\in{\mathbb F}_{2}^{n}|f(\boldsymbol{x})=1\}\). In this paper, for simplicity, and if there is no confusion, we continue to write \(supp(f)\) for the support table of \(f\), i.e., a matrix whose row vectors are elements in the support of \(f\) [12].

Let \(A=(a_{i,j})_{m\times n}\) and \(B\) be \(m\times n\) and \(p\times q\) matrices, respectively. The Kronecker product of \(A\) and \(B\) is defined as the \(mp\times nq\) matrix \(A\otimes B=(a_{i,j}B)_{mp\times nq}\). Let \(A^{\mathrm{T}}\) be the transpose of the matrix \(A\), and let \(\lfloor n\rfloor\) denote the largest integer less than or equal to \(n\), i.e., \(n-1\leq\lfloor n\rfloor \leq n\). Let \(\mathbf{1}_{k}\) be the \(k\times 1\) vector of \(1s\), and \(\mathbf{0}_{k}\) be the \(k\times 1\) vector of \(0s\). To avoid confusion, we denote the sum over \(\mathbb{Z}\) by \(+\), and the sum over \(\mathbb{F}_{2}\) by \(\oplus\). Given a vector \(\boldsymbol{x}=(x_{0},x_{1},\cdots,x_{n-1})\in{\mathbb F}_{2}^{n}\), we define its support as the set \(supp(\boldsymbol{x})=\{0\leq i\leq n-1|x_{i}=1\}\), and its Hamming weight as \(\texttt{wt}(\boldsymbol{x})=x_{0}+x_{1}+\cdots+x_{n-1}\). We denote by \(\overline{\boldsymbol{x}}=(x_{0}\oplus 1,x_{1}\oplus 1,\cdots,x_{n-1}\oplus 1)\) the complement of \(\boldsymbol{x}\). For \(0\leq k\leq n-1\), we define

\[\rho_{n}^{k}(x_{i})=\left\{ \begin{array}{ll} x_{i+k}, & \hbox{if$~i+k<n$;} \\ x_{i+k-n}, & \hbox{if$~i+k\geq n$,} \end{array} \right.\]

where \(x_{i}\in \mathbb{F}_{2}\) and \(0\leq i\leq n-1\). We can also extend the definition of \(\rho_{n}^{k}\) to \(n\)-tuples as \(\rho_{n}^{k}(x_{0},x_{1},\cdots,x_{n-1})=(\rho_{n}^{k}(x_{0}),\rho_{n}^{k}(x_{1}),\cdots,\rho_{n}^{k}( _{n-1})).\)

Definition 1 [3], [4] For \(f\in \textbf{B}_{n}\), if \(f(\rho_{n}^{k}(x_{0},x_{1},\cdots, x_{n-1}))=f(x_{0},x_{1},\cdots,x_{n-1})\) holds for any \(0\leq k\leq n-1\) and \((x_{0},x_{1},\cdots,x_{n-1})\in \mathbb{F}_{2}^{n}\), then \(f\) is called a rotation symmetric Boolean function \((\mathrm{RSBF})\). We denote by \(\textbf{RSBF}_{n}\) the set of all the \(n\)-variable RSBFs.

Definition 2 [4], [5], [11], [12] The orbit generated by \(\boldsymbol{x}\in {\mathbb F}_{2}^{n}\) under the action of cyclic group \(C_{n}=\{\rho_{n}^{k}|0\leq k\leq n-1\}\) is defined as \(O_{n}(\boldsymbol{x})=\{\rho_{n}^{k}(\boldsymbol{x})|\boldsymbol{x}\in{\mathbb {F}_{2}^{n}},0\leq k\leq n-1\}\). If \(|O_{n}(\boldsymbol{x})|=n\), we say \(O_{n}(\boldsymbol{x})\) is a long orbit, and if \(|O_{n}(\boldsymbol{x})|=l<n\), we call it a short orbit.

In this paper, \(O_{n}(\boldsymbol{x})\) also represents the following orbit matrix when no confusion can arise [12]-[15],

\[\begin{align} O_{n}(\boldsymbol{x})&=\left( \begin{array}{c} \rho_{n}^{0}(\boldsymbol{x}) \\ \rho_{n}^{1}(\boldsymbol{x}) \\ \vdots \\ \rho_{n}^{l-1}(\boldsymbol{x}) \\ \end{array} \right)=\left( \begin{array}{cccc} x_{0} & x_{1} & \cdots & x_{n-1} \\ x_{1} & x_{2} & \cdots & x_{0} \\ \vdots & \vdots & \ddots & \vdots \\ x_{l-1} & x_{l} & \cdots & x_{l-2} \\ \end{array} \right) \tag{1} \\ \nonumber &=(X_{0},X_{1},\cdots ,X_{n-1}), \end{align}\]

where \(|O_{n}(\boldsymbol{x})|=l\), \(l|n\). If \(|O_{n}(\boldsymbol{x})|=n\), it is clear that \(O_{n}(\boldsymbol{x})\) is a symmetric matrix.

If \(|O_{n}(\boldsymbol{x})|=l<n\) satisfies \(n=tl\), then \(\boldsymbol{x}=\textbf{1}_{t}^{\mathrm{T}}\otimes(x_{0},x_{1},\cdots,x_{l-1})\) and \(O_{n}(\boldsymbol{x})=\textbf{1}_{t}^{\mathrm{T}}\otimes(X_{0},X_{1},\cdots,X_{l-1})\). Assume that \(\widetilde{O_{n}}(\boldsymbol{x})=\textbf{1}_{t} \otimes O_{n}(\boldsymbol{x})\). It is easily seen that the number of the rows of \(\widetilde{O_{n}}(\boldsymbol{x})\) is \(n\), then the matrix \(\widetilde{O_{n}}(\boldsymbol{x})\) can be seen as a long orbit, which is given by the matrix \(O_{n}(\boldsymbol{x})\).

Definition 3 [14] Let \(O_{n}(\boldsymbol{x})=(X_{0},X_{1},\cdots ,X_{n-1})\) for \(\boldsymbol{x}\in {\mathbb F}_{2}^{n}\), where \(X_{i}\) is the \((i+1)\)-th column vector of \(O_{n}(\boldsymbol{x})\). Let \(b_{i1}\), \(b_{i2}\) and \(b_{i3}\) denote respectively the number of times that \(2\)-tuples, i.e., \(00\), \(01(10)\) and \(11\), appear in the row vectors of \((X_{0},X_{i})\), where \(1\leq i \leq \lfloor \frac{n}{2}\rfloor\), then the following matrix is called the \(2\)-tuples distribution matrix of \(O_{n}(\boldsymbol{x})\),

\[\begin{align} B_{O_{n}(\boldsymbol{x})}&=\left( \begin{array}{ccc} b_{11} & b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \\ \vdots & \vdots & \vdots \\ b_{\lfloor \frac{n}{2}\rfloor1} & b_{\lfloor \frac{n}{2}\rfloor2} & b_{\lfloor \frac{n}{2}\rfloor3} \\ \end{array} \right) =\left( \begin{array}{c} {\beta}_{1} \\ \beta_{2} \\ \vdots \\ \beta_{\lfloor \frac{n}{2}\rfloor} \\ \end{array} \right) \tag{2} \\ \nonumber &=(\boldsymbol{b}_{1}, \boldsymbol{b}_{2}, \boldsymbol{b}_{3}) \end{align}\]

where \(\boldsymbol{b}_{i}\) is the \(i\)-th column vector of \(B_{O_{n}(\boldsymbol{x})}\) for \(1\leq i \leq 3\) and \(\beta_{j}\) is the \(j\)-th row vector of \(B_{O_{n}(\boldsymbol{x})}\) for \(1\leq j \leq \lfloor \frac{n}{2}\rfloor\).

Moreover, \(B_{ O_{n}(\boldsymbol{x})\bigcup O_{n}(\boldsymbol{y})}=B_{O_{n}(\boldsymbol{x})}+B_{O_{n}(\boldsymbol{y})}\) if \(O_{n}(\boldsymbol{x})\neq O_{n}(\boldsymbol{y})\), where \(\boldsymbol{x}, \boldsymbol{y}\in \mathbb{F}_{2}^{n}\), and it is easy to verify that \(B_{O_{n}(\overline{\boldsymbol{x}})}=(\boldsymbol{b}_{3}, \boldsymbol{b}_{2}, \boldsymbol{b}_{1}).\)

Definition 4 [16] Let \(\boldsymbol{a}=(a_{0},a_{1},\cdots,a_{n-1},\cdots)\) be a sequence with the period \(n\), where \(a_{i}\in{\mathbb F}_{2}\). If the elements of a sequence \(\boldsymbol{b}=\{b_{i}\}\) are defined by

\[b_{i}=a_{si},~\forall i\geq 0,\]

then \(\boldsymbol{b}\) is called an \(s\)-decimation sequence of \(\boldsymbol{a}\), denoted by \(\boldsymbol{b}=\boldsymbol{a}^{(s)}\), where the period of \(s\)-decimation \(\boldsymbol{a}^{(s)}\) is \(n/(s,n)\).

For simplicity, we also regard \(\boldsymbol{a}\) with the period \(n\) as vectors over \({\mathbb F}_{2}^{n}\), i.e., \(\boldsymbol{a}=(a_{0},a_{1},\cdots,a_{n-1})\).

Definition 5 [17] An \(N\times n\) array \(A\) with entries from \(\mathbb{F}_{2}\) is said to be an orthogonal array with \(2\) levels, strength \(t\) and index \(\lambda\) if every \(N\times t\) subarray of \(A\) contains each \(t\)-tuples based on \(\mathbb{F}_{2}\) exactly \(\lambda\) times as a row. We will denote such an array by \(\mathrm{OA}(N,n,2,t)\).

3.  Properties of \(2\)-Tuples Distribution Matrix

In this section we will further analyze the basic properties of \(2\)-tuples distribution matrix.

Lemma 1 [13] For each \(\boldsymbol{x}\in{\mathbb F}_{2}^{n}\), suppose that \(O_{n}(\boldsymbol{x})\) is defined by \((1)\). Define

\[\widehat{B}_{O_{n}(\boldsymbol{x})}=\left( \begin{array}{@{\hskip2pt}ccc@{\hskip2pt}} b_{11} & b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \\ \vdots & \vdots & \vdots \\ b_{(n-1)1} & b_{(n-1)2} & b_{(n-1)3} \\ \end{array} \right)= \left( \begin{array}{@{\hskip2pt}c@{\hskip2pt}} \beta_{1} \\ \beta_{2} \\ \vdots \\ \beta_{n-1} \\ \end{array} \right),\]

and let \(b_{i1}\), \(b_{i2}\) and \(b_{i3}\) denote respectively the number of times that \(2\)-tuples, i.e., \(00\), \(01(10)\) and \(11\), appear in the row vectors of \((X_{0},X_{i})\) for \(1\leq i\leq n-1\), where \(\beta_{i}\) is the \(i\)-th row vector of \(\widehat{B}_{O_{n}(\boldsymbol{x})}\). Then \(\beta_{i}=\beta_{n-i}\).

Property 1\(\quad\)Suppose that \(O_{n}(\boldsymbol{x})\) and \(B_{O_{n}(\boldsymbol{x})}\) are defined by \((1)\) and \((2)\), where \(\boldsymbol{x}\in{\mathbb F}_{2}^{n}\). If \(\texttt{wt}(\boldsymbol{x})=\omega\) and \(|O_{n}(\boldsymbol{x})|=l\) satisfies \(n=tl\), where \(t\) is a positive integer, then \(\boldsymbol{b}_{1}-\boldsymbol{b}_{3}=\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(\frac{n-2\omega}{t})\), \(\boldsymbol{b}_{1}+\boldsymbol{b}_{2}=\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(\frac{n-\omega}{t})\) and \(\boldsymbol{b}_{2}+\boldsymbol{b}_{3}=\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(\frac{\omega}{t})\).

Proof. If \(t=1\), we have \(|O_{n}(\boldsymbol{x})|=n\). According to Definition 3, it is easy to know that \(b_{i1}+b_{i2}=n-\omega\) and \(b_{i2}+b_{i3}=\omega\), which leads to \(b_{i1}-b_{i3}=n-2\omega\). Hence, \(\boldsymbol{b}_{1}-\boldsymbol{b}_{3}=\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(n-2\omega),~ \boldsymbol{b}_{1}+\boldsymbol{b}_{2}=\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(n-\omega)~\mathrm{and}~ \boldsymbol{b}_{2}+\boldsymbol{b}_{3}=\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(\omega).\)

If \(t>1\), we have \(|O_{n}(\boldsymbol{x})|=l<n\). Assume that \(\widetilde{O_{n}}(\boldsymbol{x})=\textbf{1}_{t} \otimes O_{n}(\boldsymbol{x})\), then we continue in the same way as above. Obviously, \(t(b_{i1}+b_{i2})=n-\omega\) and \(t(b_{i2}+b_{i3})=\omega\). We get \(t(b_{i1}-b_{i3})=n-2\omega\). Thus, \(\boldsymbol{b}_{1}-\boldsymbol{b}_{3}=\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(\frac{n-2\omega}{t}),~~ \boldsymbol{b}_{1}+\boldsymbol{b}_{2}=\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(\frac{n-\omega}{t})~~\mathrm{and}~~ \boldsymbol{b}_{2}+\boldsymbol{b}_{3}=\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(\frac{\omega}{t})\). \(\tag*{◻}\)

Property 2\(\quad\)Let \(n\) be prime, \(O_{n}(\boldsymbol{x})\) and \(B_{O_{n}(\boldsymbol{x})}\) be defined by \((1)\) and \((2)\) for \(\boldsymbol{x}\in{\mathbb F}_{2}^{n}\), and let \(\boldsymbol{x}^{(s)}\) be \(s\)-decimation of \(\boldsymbol{x}\), where \(1\leq s\leq n-1\). Then \(B_{O_{n}(\boldsymbol{x}^{(s)})}=B_{O_{n}(\boldsymbol{x}^{(n-s)})}\) and the row vectors of \(B_{O_{n}(\boldsymbol{x}^{(s)})}\) are the permutations of the row vectors of \(B_{O_{n}(\boldsymbol{x})}\).

Proof. On the one hand, recall that \(\boldsymbol{x}^{(s)}=(x_{0},x_{s(\mathrm{mod}~n)},x_{2s(\mathrm{mod}~n)}, \cdots,x_{(n-1)s(\mathrm{mod}~n)})\). We have

\[B_{O_{n}(\boldsymbol{x}^{(s)})}\!=\!\left( \begin{array}{@{\hskip2pt}c@{\hskip2pt}} \beta_{s(\mathrm{mod}~n)} \\ \beta_{2s(\mathrm{mod}~n)} \\ \vdots \\ \beta_{\lfloor \frac{n}{2}\rfloor s(\mathrm{mod}~n)} \\ \end{array} \right),~B_{O_{n}(\boldsymbol{x}^{(n-s)})}\!=\!\left( \begin{array}{@{\hskip2pt}c@{\hskip2pt}} \beta_{(n-s)(\mathrm{mod}~n)} \\ \beta_{2(n-s)(\mathrm{mod}~n)} \\ \vdots \\ \beta_{\lfloor \frac{n}{2}\rfloor (n-s)(\mathrm{mod}~n)} \\ \end{array} \right)\!.\]

From \(\beta_{i}=\beta_{n-i}\) we get \(B_{O_{n}(\boldsymbol{x}^{(s)})}=B_{O_{n}(\boldsymbol{x}^{(n-s)})}\).

On the other hand, obviously \(is\not\equiv js(\mathrm{mod}~n)\) for any \(1\leq j<i\leq \lfloor \frac{n}{2}\rfloor\). Moreover, we have \(is(\mathrm{mod}~n)+js(\mathrm{mod}~n)\neq n\). Otherwise, \((i+j)s\equiv 0(\mathrm{mod}~n)\). It follows that \(i=n-j\), which contradicts with \(1\leq j<i\leq \lfloor \frac{n}{2}\rfloor\). Thus, by \(\beta_{i}=\beta_{n-i}\) for \(1\leq i\leq n-1\), the set \(\{\beta_{s(\mathrm{mod}~n)},\beta_{2s(\mathrm{mod}~n)},\cdots,\beta_{\lfloor \frac{n}{2}\rfloor s(\mathrm{mod}~n)}\}\) is equal to the set \(\{\beta_{1},\beta_{2},\cdots, \beta_{\lfloor \frac{n}{2}\rfloor}\}\) for \(1\leq s\leq \lfloor \frac{n}{2}\rfloor\). Then the row vectors of \(B_{O_{n}(\boldsymbol{x}^{(s)})}\) are the permutations of the row vectors of \(B_{O_{n}(\boldsymbol{x})}\). \(\tag*{◻}\)

Remark 1\(\quad\)With the help of Property \(2\), it can be easily verified that if \(B_{O_{n}(\boldsymbol{x})}\) has two different row vectors, then \(B_{O_{n}(\boldsymbol{x}^{(1)})}, B_{O_{n}(\boldsymbol{x}^{(2)})},\cdots,\) \(B_{O_{n}(\boldsymbol{x}^{(\lfloor \frac{n}{2}\rfloor)})}\) are different from each other.

For any \(\boldsymbol{x}\in{\mathbb F}_{2}^{n}\), given \(O_{n}(\boldsymbol{x})\) and \(B_{O_{n}(\boldsymbol{x})}\) by \((1)\) and \((2)\). Let \(n\) be an odd prime, \(\boldsymbol{x}^{(s)}\) be \(s\)-decimation of \(\boldsymbol{x}\), where \(1\leq s\leq \lfloor\frac{n}{2}\rfloor\), and let \(S=\{i_{1},i_{2},\cdots,i_{m}\}\subseteq T=\{1,2,3,\cdots,\lfloor\frac{n}{2}\rfloor\}\).

Property 3\(\quad\)Let the notions and symbols be defined as before, we have

\[\sum_{i\in T}B_{O_{n}(\boldsymbol{x}^{(i)})} =\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(\sum_{i\in T}b_{i1},\sum_{i\in T}b_{i2},\sum_{i\in T}b_{i3}).\]

Proof. According to Lemma \(1\) and Property \(2\), we have

\[\begin{aligned} \sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}B_{O_{n}(\boldsymbol{x}^{(i)})} &\!=\!\frac{1}{2}\sum_{i=1}^{n-1}B_{O_{n}(\boldsymbol{x}^{(i)})}\!=\! \textbf{1}_{\lfloor\frac{n}{2}\rfloor} \otimes\frac{1}{2}(\beta_{1}\!+\!\beta_{2}\!+\!\cdots\!+\!\beta_{n-1})\\ &\!=\!\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(\beta_{1}+\beta_{2} +\cdots\beta_{\lfloor\frac{n}{2}\rfloor})\\ &\!=\!\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(\sum_{i\in T}b_{i1},\sum_{i\in T}b_{i2},\sum_{i\in T}b_{i3}). \end{aligned}\]

\(\tag*{◻}\)

Property 4\(\quad\)Let the notions and symbols be defined as before. Suppose that \(\boldsymbol{x}\in{\mathbb F}_{2}^{n}\) and \(\texttt{wt}(\boldsymbol{x})=\omega\), then

\[\sum_{i\in S}B_{O_{n}(\overline{\boldsymbol{x}}^{(i)})}+\sum_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}^{(i)})} =\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(\mu_{1},\mu_{2},\mu_{3}),\]

where \(\mu_{1}=\sum\limits_{i\in T}b_{i1}-m(n-2\omega)\), \(\mu_{2}=\sum\limits_{i\in T}b_{i2}\) and \(\mu_{3}=\sum\limits_{i\in T}b_{i3}+m(n-2\omega)\).

Proof. From Definition \(3\) we have

\[B_{O_{n}(\overline{\boldsymbol{x}})}-B_{O_{n}(\boldsymbol{x})} =\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(2\omega-n,0,n-2\omega).\]

It’s easy to verify that \(\overline{\boldsymbol{x}^{(s)}}=\overline{\boldsymbol{x}}^{(s)}\). Thus,

\[\begin{aligned} &\sum_{i\in S}B_{O_{n}(\overline{\boldsymbol{x}}^{(i)})}+\sum_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}^{(i)})} =\sum_{i\in S}B_{O_{n}(\overline{\boldsymbol{x}^{(i)}})}+\sum_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}^{(i)})}\\ &=\sum_{i\in S}\big(B_{O_{n}(\overline{\boldsymbol{x}^{(i)}})}-B_{O_{n}(\boldsymbol{x}^{(i)})}\big)+\sum_{i\in T}B_{O_{n}(\boldsymbol{x}^{(i)})}\\ &=\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\!\otimes\!(\sum_{i\in T}b_{i1}-m(n-2\omega), \sum_{i\in T}b_{i2},\sum_{i\in T}b_{i3}\!+\!m(n-2\omega)). \end{aligned}\]

\(\tag*{◻}\)

Property 5\(\quad\)Let \(n\) be odd, \(O_{n}(\boldsymbol{x})\) and \(B_{O_{n}(\boldsymbol{x})}\) be defined by \((1)\) and \((2)\) for \(\boldsymbol{x}\in{\mathbb F}_{2}^{n}\). Suppose that \(\texttt{wt}(\boldsymbol{x})=\omega\) and \(|O_{n}(\boldsymbol{x})|=l\) satisfies \(n=tl\), where \(t\) is a positive integer, then

\[\mbox{$\displaystyle \sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}b_{i1}\!=\!\frac{(n\!-\!\omega)(n\!-\!\omega\!-\!1)}{2t},~ \sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}b_{i2}\!=\!\frac{\omega(n\!-\!\omega)}{2t},~\sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}b_{i3}\!=\!\frac{\omega(\omega\!-\!1)}{2t}. $}\]

Proof. If \(t=1\), we have \(|O_{n}(\boldsymbol{x})|=n\). By \((1)\), write \(X_{0}^{\textrm{T}}X_{i}=x_{0}x_{i}+x_{1}x_{i+1}+\cdots+x_{n-1}x_{i-1}\), where \(1\leq i\leq n-1\). Then \(\sum_{i=1}^{n-1}X_{0}^{\textrm{T}}X_{i} =\sum_{i=0}^{n-1}x_{i}(x_{0}+\cdots+x_{i-1}+x_{i+1}+\cdots+x_{n-1}) =\omega(\omega\!-\!1).\) It’s easy to see that \(\sum_{i=1}^{n-1}X_{0}^{\textrm{T}}X_{i}\) represents the number of vector \((1,1)\) in \((X _{0},X_{l})\) for all \(1\leq l\leq n-1\). By Definition 3 and Lemma 1, we have \(\sum_{i=1}^{n-1}X_{0}^{\textrm{T}}X_{i}=2\sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}b_{i3}\). So \(\sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}b_{i3}=\frac{1}{2}\omega(\omega-1)\). Note that \(b_{i1}+b_{i2}=n-\omega\) and \(b_{i2}+b_{i3}=\omega\). Then \(\sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}(b_{i1}+b_{i2})=\lfloor \frac{n}{2}\rfloor(n-\omega)\) and \(\sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}(b_{i2}+b_{i3})=\lfloor \frac{n}{2}\rfloor\omega.\) Hence,

\[\sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}b_{i2} =\frac{1}{2}\omega(n-\omega),~ \sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}b_{i1} =\frac{1}{2}(n-\omega)(n-\omega-1).\]

If \(t>1\), we have \(|O_{n}(\boldsymbol{x})|=l<n\). Write \(\widetilde{O_{n}}(\boldsymbol{x})=\textbf{1}_{t} \otimes O_{n}(\boldsymbol{x})\). Then we have

\[B_{\widetilde{O_{n}}(\boldsymbol{x})}=\left( \begin{array}{@{\hskip2pt}ccc@{\hskip2pt}} \widetilde{b}_{11} & \widetilde{b}_{12} & \widetilde{b}_{13} \\ \widetilde{b}_{21} & \widetilde{b}_{22} & \widetilde{b}_{23} \\ \vdots & \vdots & \vdots \\ \widetilde{b}_{\lfloor \frac{n}{2}\rfloor1} & \widetilde{b}_{\lfloor \frac{n}{2}\rfloor2} & \widetilde{b}_{\lfloor \frac{n}{2}\rfloor3} \\ \end{array} \right).\]

It is easy to see that \(\widetilde{b}_{ij}=tb_{ij}\), where \(1\leq i\leq \lfloor \frac{n}{2}\rfloor\) and \(1\leq j\leq3\). Therefore,

\[\mbox{$\displaystyle \sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}b_{i1}\!=\!\frac{(n\!-\!\omega)(n\!-\!\omega\!-\!1)}{2t},~ \sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}b_{i2}\!=\!\frac{\omega(n\!-\!\omega)}{2t},~\sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}b_{i3}\!=\!\frac{\omega(\omega\!-\!1)}{2t}. $}\]

\(\tag*{◻}\)

4.  Constructions of 2-Correlation Immune RSBFs

Lemma 2 [12] Let \(f\in \textbf{RSBF}_{n}\) and its support table be \(supp(f)=(c_{0}, c_{1},\cdots, c_{n-1})\), where \(c_{i}\) is the \((i+1)\)-th column vector of \(supp(f)\). Then \(f\) is \(2\)-CI if and only if \((c_{0},c_{l})\) is an \(\mathrm{OA}(|supp(f)|,2,2,2)\), where \(1\leq l\leq \lfloor \frac{n}{2}\rfloor\).

Based on \(2\)-tuples distribution matrix, we privide a new sufficient and necessary condition of \(2\)-correlation immune RSBFs as follows:

Theorem 1\(\quad\)Let \(f\in \textbf{RSBF}_{n}\). Then \(f\) is \(2\)-CI if and only if the \(2\)-tuples distribution matrix of its support table \(supp(f)\) satisfies

\[\begin{equation*} B_{supp(f)}=\left( \begin{array}{ccc} k & k & k \\ k & k & k \\ \vdots & \vdots & \vdots \\ k & k & k \\ \end{array} \right)_{\lfloor\frac{n}{2}\rfloor\times3} =\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes (k,k,k), \tag{3} \end{equation*}\]

where \(k=\frac{|supp(f)|}{4}\).

Proof. Assume that \(f\) is a \(2\)-CI, then \((c_{0},c_{l})\) is an \(\mathrm{OA}(|supp(f)|,2,2,2)\) by Lemma \(2\), where \(1\leq l\leq \lfloor \frac{n}{2}\rfloor\). Thus, the numbers of (0,0), (0,1), (1,0) and (1,1) in \((c_{0},c_{l})\) are all \(|supp(f)|/4\). According to Definition \(3\), we have \(B_{supp(f)}=\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes (k,k,k)\), where \(k=\frac{|supp(f)|}{4}\).

Conversely, if \(B_{supp(f)}=\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes (k,k,k)\), where \(k=\frac{|supp(f)|}{4}\), then it is easy to know that \((c_{0},c_{l})\) is an \(\mathrm{OA}(|supp(f)|,2,2,2)\) from Definitions \(3\) and \(5\), where \(1\leq l\leq \lfloor \frac{n}{2}\rfloor\). Hence, by Lemma \(2\), \(f\) is \(2\)-CI. \(\tag*{◻}\)

Remark 2\(\quad\) When \(k=2^{n-3}\), \(f(\boldsymbol{x})\) is a \(2\)-resilient RSBF.

By Theorem 1, we know that constructing \(2\)-correlation immune RSBFs is equivalent to finding the union of several orbits such that the sum of their corresponding \(2\)-tuples distribution matrices is the matrix in \((3)\). In order to construct \(2\)-correlation immune RSBFs, we demonstrate four distinct classes of \(2\)-tuples distribution matrices as follows:

1. For \(\boldsymbol{x}\in \mathbb{F}_{2}^{n}\), if \(\texttt{wt}(\boldsymbol{x})=1\), then the \(2\)-tuples distribution matrix of \(O_{n}(\boldsymbol{x})\) is

   \[\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes (n-2,1,0).\]

2. Let \(n=4t-1\) be a prime and \(t\geq 2\) be an integer. We can get a vector \(\boldsymbol{x}\in \mathbb{F}_{2}^{n}\) from the cyclic Hadamard matrix [18] \(H_{(n+1)\times (n+1)}\), and the method of obtaining \(\boldsymbol{x}\) is described in Sect. 3 of [15], where \(\texttt{wt}(\boldsymbol{x})=2t\) and the \(2\)-tuples distribution matrix of \(O_{n}(\boldsymbol{x})\) is

   \[\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes (t-1, t, t).\]

3. Let \(n\) be odd prime. By Properties 3 and 5, we get

   \[\sum_{s\in T}\!B_{O_{n}(\boldsymbol{x}^{(s)})}\!=\!\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes \frac{1}{2}\big((n\!-\!\omega)(n\!-\!\omega\!-\!1) , \omega(n\!-\!\omega) , \omega(\omega\!-\!1)\big).\]

4. Let \(n\) be odd prime. By Properties \(4\) and \(5\), we obtain

   \[\begin{aligned} \sum_{j\in S}B_{O_{n}(\overline{\boldsymbol{x}}^{(j)})}+\sum_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}^{(i)})} =\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes (\mu_{1} , \mu_{2}, \mu_{3}), \end{aligned}\]

   where \(\mu_{1}=\frac{1}{2}(n-\omega)(n-\omega-1)-m(n-2\omega)\), \(\mu_{2}=\frac{1}{2}\omega(n-\omega)\) and \(\mu_{3}=\frac{1}{2}\omega(\omega-1)+m(n-2\omega)\).

Next we will construct 2-correlation immune RSBFs based on these four \(2\)-tuples distribution matrices.

Construction. Let \(n=4t-1\) be a prime and \(t\), \(m\) be positive integers.

It is easy to see that the orbits that correspond to these four \(2\)-tuples distribution matrices mentioned above are all long orbits, then we have \(|supp(f)|=n(n+1)\). Let \(T=\{1,2,\cdots,\lfloor\frac{n}{2}\rfloor\}\), \(S=\{i_{1},i_{2},\cdots,i_{m}\}\subseteq T\), \(S'=\{j_{1},j_{2},\cdots,j_{l}\}\subseteq T\) and \(k=\frac{n(n+1)}{4}\). Let \(\boldsymbol{x}_{1}=(1,0,0,\cdots,0,0)\in {\mathbb F}_{2}^{n}\), and let \(\boldsymbol{x}_{2}\) be obtained from a cyclic Hadamard matrix of order \(n+1\). Suppose that both \(B_{O_{n}(\boldsymbol{x}_{3})}\) and \(B_{O_{n}(\boldsymbol{x}_{4})}\) have two different row vectors, where \(\texttt{wt}(\boldsymbol{x}_{3})=\omega_{1}\), \(\texttt{wt}(\boldsymbol{x}_{4})=\omega_{2}\). We have the following Theorem \(2\).

Theorem 2\(\quad\)Let the notions be defined as before. If there exist \(\omega_{1}\), \(\omega_{2}\) and \(m\) such that one of the following equations holds, then \(2\)-correlation immune RSBFs can be obtained.

• \((\mathit{1})\)  \(B_{O_{n}(\boldsymbol{x}_{1})}+B_{O_{n}(\boldsymbol{x}_{2})}+\sum\limits_{i\in T}B_{O_{n}(\boldsymbol{x}_{3}^{(i)})} +\sum\limits_{i\in S}B_{O_{n}(\overline{\boldsymbol{x}_{4}}^{(i)})}+\sum\limits_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}_{4}^{(i)})} =\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(k,k,k)\);

• \((\mathit{2})\)  \(B_{O_{n}(\overline{\boldsymbol{x}_{1}})}+B_{O_{n}(\boldsymbol{x}_{2})}+\sum\limits_{i\in T}B_{O_{n}(\boldsymbol{x}_{3}^{(i)})} +\sum\limits_{i\in S}B_{O_{n}(\overline{\boldsymbol{x}_{4}}^{(i)})}+\sum\limits_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}_{4}^{(i)})} =\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(k,k,k)\);

• \((\mathit{3})\)  \(B_{O_{n}(\boldsymbol{x}_{1})}+B_{O_{n}(\overline{\boldsymbol{x}_{2}})}+\sum\limits_{i\in T}B_{O_{n}(\boldsymbol{x}_{3}^{(i)})} +\sum\limits_{i\in S}B_{O_{n}(\overline{\boldsymbol{x}_{4}}^{(i)})}+\sum\limits_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}_{4}^{(i)})} =\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(k,k,k)\);

• \((\mathit{4})\)  \(B_{O_{n}(\overline{\boldsymbol{x}_{1}})}+B_{O_{n}(\overline{\boldsymbol{x}_{2}})}+\sum\limits_{i\in T}B_{O_{n}(\boldsymbol{x}_{3}^{(i)})} +\sum\limits_{i\in S}B_{O_{n}(\overline{\boldsymbol{x}_{4}}^{(i)})}+\sum\limits_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}_{4}^{(i)})} =\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(k,k,k)\);

• \((\mathit{5})\)  \(B_{O_{n}(\boldsymbol{x}_{1})}+B_{O_{n}(\boldsymbol{x}_{2})} +\sum\limits_{i\in S'}B_{O_{n} (\overline{\boldsymbol{x}_{3}}^{(i)})}+\sum\limits_{i\in T\backslash S'}B_{O_{n}(\boldsymbol{x}_{3}^{(i)})} +\sum\limits_{i\in S}B_{O_{n}(\overline{\boldsymbol{x}_{4}}^{(i)})}+\sum\limits_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}_{4}^{(i)})} =\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(k,k,k)\);

• \((\mathit{6})\)  \(B_{O_{n}(\overline{\boldsymbol{x}_{1}})}+B_{O_{n}(\boldsymbol{x}_{2})}+\sum\limits_{i\in S'}B_{O_{n}(\overline{\boldsymbol{x}_{3}}^{(i)})}+\sum\limits_{i\in T\backslash S'}B_{O_{n}(\boldsymbol{x}_{3}^{(i)})} +\sum\limits_{i\in S}B_{O_{n}(\overline{\boldsymbol{x}_{4}}^{(i)})}+\sum\limits_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}_{4}^{(i)})} =\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(k,k,k)\);

• \((\mathit{7})\)  \(B_{O_{n}(\boldsymbol{x}_{1})}+B_{O_{n}(\overline{\boldsymbol{x}_{2}})}+\sum\limits_{i\in S'}B_{O_{n} (\overline{\boldsymbol{x}_{3}}^{(i)})}+\sum\limits_{i\in T\backslash S'}B_{O_{n}(\boldsymbol{x}_{3}^{(i)})} +\sum\limits_{i\in S}B_{O_{n}(\overline{\boldsymbol{x}_{4}}^{(i)})}+\sum\limits_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}_{4}^{(i)})} =\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(k,k,k)\);

• \((\mathit{8})\)  \(B_{O_{n}(\overline{\boldsymbol{x}_{1}})} +B_{O_{n}(\overline{\boldsymbol{x}_{2}})}+\sum\limits_{i\in S'}B_{O_{n} (\overline{\boldsymbol{x}_{3}}^{(i)})}+\sum\limits_{i\in T\backslash S'}B_{O_{n}(\boldsymbol{x}_{3}^{(i)})} +\sum\limits_{i\in S}B_{O_{n}(\overline{\boldsymbol{x}_{4}}^{(i)})}+\sum\limits_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}_{4}^{(i)})} =\mathbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(k,k,k)\).

Proof. We give the proof only for equation \((\mathit{1})\), the rest of the cases is similar.

It is easy to check that the sum of these four \(2\)-tuples distribution matrices is as follows:

\[\begin{aligned} &~~~~ \mbox{$\displaystyle B_{O_{n}(\boldsymbol{x}_{1})}+B_{O_{n}(\boldsymbol{x}_{2})}+\sum\limits_{i\in T}B_{O_{n}(\boldsymbol{x}_{3}^{(i)})} +\sum\limits_{i\in S}B_{O_{n}(\overline{\boldsymbol{x}_{4}}^{(i)})}+\sum\limits_{i\in T\backslash S}B_{O_{n}(\boldsymbol{x}_{4}^{(i)})} $} \\ & \mbox{$\displaystyle =\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(n-2,1,0) +\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes(t-1,t,t) $}\\ & \mbox{$\displaystyle +\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes (\frac{(n-\omega_{1})(n-\omega_{1}-1)}{2},\frac{\omega_{1}(n-\omega_{1})}{2}, \frac{\omega_{1}(\omega_{1}-1)}{2}) +\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes $}\\ &~~ \mbox{$\displaystyle \big(\frac{(n\!-\!\omega_{2})(n\!-\!\omega_{2}\!-\!1)}{2}\!-\!m(n\!-\!2\omega_{2}), \frac{\omega_{2}(n\!-\!\omega_{2})}{2}, \frac{\omega_{2}(\omega_{2}\!-\!1)}{2}+m(n\!-\!2\omega_{2})\big) $}\\ & \mbox{$\displaystyle =\textbf{1}_{\lfloor\frac{n}{2}\rfloor}\otimes M^{\mathrm{T}}, $} \end{aligned}\]

where

\[\mbox{$\displaystyle \displaystyle M=\left( \begin{array}{@{\hskip2pt}c@{\hskip2pt}} n\!+\!t\!-\!3\!+\!\frac{(n-\omega_{1})(n-\omega_{1}-1)}{2}+\frac{(n-\omega_{2}) (n-\omega_{2}-1)}{2}\!-\!m(n\!-\!2\omega_{2}) \\ t+1+\frac{\omega_{1}(n-\omega_{1})}{2}+\frac{\omega_{2}(n-\omega_{2})}{2} \\ t+\frac{\omega_{1}(\omega_{1}-1)}{2}+\frac{\omega_{1}(\omega_{2}-1)}{2} +m(n-2\omega_{2}) \\ \end{array} \right). $}\]

Suppose that the equation \((\mathit{1})\) holds, then we can obtain the following system of equations

\[\begin{equation*} \mbox{$\displaystyle \displaystyle \begin{cases} t\!-\!3\!+\!n(n\!-\!\omega_{1}\!-\!\omega_{2})\!+\!\frac{1}{2}\omega_{1}(\omega_{1}\!+\!1) \!+\!\frac{1}{2}\omega_{2}(\omega_{2}\!+\!1)\!-\!m(n\!-\!2\omega_{2})\!=\!k \\ t+1+\frac{1}{2}\omega_{1}(n-\omega_{1})+\frac{1}{2}\omega_{2}(n-\omega_{2})=k \\ t+\frac{1}{2}\omega_{1}(\omega_{1}-1)+\frac{1}{2}\omega_{2}(\omega_{2}-1)+m(n-2\omega_{2})=k \end{cases}$}\quad, \tag{4} \end{equation*}\]

where \(k=\frac{n(n+1)}{4}\) and \(1\leq m\leq \lfloor\frac{n}{2}\rfloor\) are all integers.

When \(n\) is determined, we set the values of \(\omega_{1}\) and \(\omega_{2}\) according to the system of equations, and if \(m\) has an integer solution in the above equation, we can choose the appropriate vectors \(\boldsymbol{x}_{2}\), \(\boldsymbol{x}_{3}\) and \(\boldsymbol{x}_{4}\). Let the support of \(f\in \textbf{B}_{n}\) be

\[\begin{align} supp(f)=&O_{n}(\boldsymbol{x}_{1})\bigcup O_{n}(\boldsymbol{x}_{2})\bigcup \big( \bigcup\limits_{i\in T} O_{n}(\boldsymbol{x}_{3}^{(i)})\big) \tag{5} \\ \nonumber &\bigcup \big( \bigcup\limits_{i\in S} O_{n}(\overline{\boldsymbol{x}_{4}}^{(i)})\big) \bigcup \big( \bigcup\limits_{i\in T\backslash S} O_{n}(\boldsymbol{x}_{4}^{(i)})\big). \end{align}\]

By Theorem \(1\), \(f\) is a \(2\)-correlation immune RSBF. The rest of the proof runs as before. We can also obtain \(2\)-correlation immune RSBFs if the related system of equations has solutions. \(\tag*{◻}\)

We now give a simple example that illustrates the previous construction.

Example 1\(\quad\)When \(n=11\), we have \(t=3\) and \(k=33\). Let \(f\in \textbf{B}_{n}\), \(\boldsymbol{x}_{1}=(1,0,0,0,0,0,0,0,0,0,0)\), and let \(\boldsymbol{x}_{3},\boldsymbol{x}_{4}\in{\mathbb F}_{2}^{11}\). Suppose that \(\boldsymbol{x}_{2}=(0,0,0,1,0,1,1,0,1,1,1)\) is obtained by the cyclic Hadamard matrix \(H_{12\times 12}\), and \(\texttt{wt}(\boldsymbol{x}_{3})=\omega_{1},~\texttt{wt}(\boldsymbol{x}_{4})=\omega_{2}\). From system of Eq. (4), the following system of equations is obtained.

\[\mbox{$\displaystyle \displaystyle \begin{cases} 11(11\!-\!\omega_{1}\!-\!\omega_{2})\!+\!\frac{1}{2}\omega_{1}(\omega_{1}\!+\!1) \!+\!\frac{1}{2}\omega_{2}(\omega_{2}\!+\!1)\!-\!m(11\!-\!2\omega_{2})\!=\!33 \\ 4+\frac{1}{2}\omega_{1}(11-\omega_{1})+\frac{1}{2}\omega_{2}(11-\omega_{2})=33 \\ 3\!+\!\frac{1}{2}\omega_{1}(\omega_{1}\!-\!1)\!+\!\frac{1}{2}\omega_{2} (\omega_{2}\!-\!1)\!+\!m(11\!-\!2\omega_{2})\!=\!33 \end{cases} $}\]

Firstly, we consider the the second equation of the system of equations. For \(0\leq \texttt{wt}(\boldsymbol{x})=\omega\leq 11\), we have Table 1. Clearly, we have \(\omega_{1}\neq \omega_{2}\). From Table 1, if \(\omega_{1}=5,6\), we can take \(\omega_{2}=4,7\). Conversely, if \(\omega_{1}=4,7\), then \(\omega_{2}=5,6\). Next, we consider the first and third equations of the above system of equations. We obtain one solution that \(\omega_{1}=6\), \(\omega_{2}=4\) and \(m=3\) for the above system of equations. Based on the solution, we can construct \(2\)-correlation immune RSBFs. Suppose that \(\boldsymbol{x}_{3}=(0,1,1,0,1,0,1,0,1,0,1)\) and \(\boldsymbol{x}_{4}=(1,0,0,1,0,0,1,0,0,1,0)\). It is easy to verify that both \(B_{O_{11}(\boldsymbol{x}_{3})}\) and \(B_{O_{11}(\boldsymbol{x}_{4})}\) have two different row vectors. Assume that \(S=\{i_{1},i_{2},i_{3}\}=\{1,2,4\}\subseteq T=\{1,2,3,4,5\}\), and the support of \(f\) is

\[\begin{aligned} &\mbox{$\displaystyle supp(f)\!=\!O_{11}(\boldsymbol{x}_{1})\!\cup\! O_{11}(\boldsymbol{x}_{2})\!\cup\!O_{11}(\boldsymbol{x}_{3})\!\cup\! O_{11}(\boldsymbol{x}_{3}^{(2)})\!\cup\! O_{11}(\boldsymbol{x}_{3}^{(3)})\!\cup\! O_{11}(\boldsymbol{x}_{3}^{(4)}) $}\\ &~~ \mbox{$\displaystyle \!\cup O_{11}(\boldsymbol{x}_{3}^{(5)})\!\cup\! O_{11}(\overline{\boldsymbol{x}_{4}})\!\cup\! O_{11}(\overline{\boldsymbol{x}_{4}}^{(2)})\!\cup\! O_{11}(\overline{\boldsymbol{x}_{4}}^{(4)})\!\cup\! O_{11}(\boldsymbol{x}_{4}^{(3)})\!\cup\! O_{11}(\boldsymbol{x}_{4}^{(5)}), $} \end{aligned}\]

then \(f(\boldsymbol{x})\) is a \(2\)-correlation immune RSBF by Theorem \(2\).

Table 1  The calculation of \(\omega\).

5.  Conclusion

In this paper, the properties of the \(2\)-tuples distribution matrix are further studied. And a new sufficient and necessary condition of \(2\)-CI RSBFs based on the \(2\)-tuples distribution matrix is presented. Then a new construction is obtained for prime \(n=4t-1\), and an illustrative example is also given. For further research, it is interesting to construct \(2\)-CI RSBFs for any number of variables.

References

[1] E. Filiol and C. Fontaine, “Highly nonlinear balanced Boolean functions with a good correlation-immunity,” Advances in Cryptology ― EUROCRYPT’98: International Conference on the Theory and Application of Cryptographic Techniques Espoo, Finland, Proceedings, pp.475-488, Springer Berlin Heidelberg, 1998.

[2] C. Fontaine, “On some cosets of the first-order Reed-Muller code with high minimum weight,” IEEE Trans. Inf. Theory, vol.45, no.4, pp.1237-1243, 1999.

[3] J. Pieprzyk and C. Qu, “Fast hashing and rotation symmetric functions,” J. Univers. Comput. Sci., vol.5, no.1, pp.20-31, 1999.

[4] P. Stănică, S. Maitra, and J. Clark, “Results on rotation symmetric bent and correlation immune Boolean functions,” International Workshop on Fast Software Encryption, Lecture Notes in Computer Science, vol.3017, pp.161-177, Springer, Berlin, Heidelberg, 2004.

[5] T.W. Cusick and P. Stanica, Cryptographic Boolean Functions and Applications, Academic Press, 2017.

[6] T. Siegenthaler, “Correlation attacks on certain stream ciphers with nonlinear generators,” IEEE Int. Symp. Inform. Theory, Saint Jovite, Canada, pp.26-29, 1983.

[7] G.-Z. Xiao and J.L. Massey, “A spectral characterization of correlation-immune combining functions,” IEEE Trans. Inf. Theory, vol.34, no.3, pp.569-571, 1988.

[8] R.A. Rueppel, Analysis and Design of Stream Ciphers, Springer, Berlin, 1986.

[9] T. Siegenthaler, “Decrypting a class of stream ciphers using ciphertext only,” IEEE Trans. Comput., vol.C-34, no.1, pp.81-85, 1985.

[10] C.R. Rao, “Factorial experiments derivable from combinatorial arrangements of arrays,” Suppl. J. R. Stat. Soc., vol.9, no.1, pp.128-139, 1947.

[11] S. Fu, C. Li, and L. Qu, “On the number of rotation symmetric Boolean functions,” Sci. China Inf. Sci., vol.53, pp.537-545, 2010.

[12] J. Du, Q. Wen, J. Zhang, and S. Pang, “Constructions of resilient rotation symmetric Boolean functions on given number of variables,” IET Inf. Secur., vol.8, no.5, pp.265-272, 2014.

[13] J. Du, C. Liu, and S. Pang, “Constructions of rotation symmetric 2-resilient functions with 4t - 1 number of variables,” J. Commun., vol.41, no.11, pp.169-175, 2020 (in Chinese).

[14] J. Du, Z. Chen, L. Dong, T. Wang, and S. Pang, “A new characterization of 2-resilient rotation symmetric Boolean functions,” IEICE Trans. Fundamentals., vol.E106-A, no.9, pp.1268-1271, Sept. 2023.

[15] J. Du, Z. Chen, S. Fu, L. Qu, and C. Li, “Constructions of 2-resilient rotation symmetric Boolean functions through symbol transformations of cyclic Hadamard matrix,” Theor. Comput. Sci., vol.919, pp.80-91, 2022.

[16] S.W. Golomb and G. Gong, Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar, Cambridge University Press, 2005.

[17] A.S. Hedayat, N.J.A. Sloane, and J. Stufken, Orthogonal Arrays: Theory and Applications, Springer Science, 1999.

[18] C. Shi and B. Tang, “Designs from good Hadamard matrices,” Bernoulli, vol.24, no.1, pp.661-671, 2018.

Authors

Jiao DU
  Henan Normal University,Beijing University of Posts and Telecommunications

Ziwei ZHAO
  Henan Normal University,Beijing University of Posts and Telecommunications

Shaojing FU
  National University of Defense Technology

Longjiang QU
  National University of Defense Technology

Chao LI
  National University of Defense Technology

Keyword

rotation symmetric boolean function,  correlation immune,  support table,  2-tuples distribution matrix