Implementing Symmetric Cryptography Using Sequence of Semi-Bent Functions

Abstract

Symmetric cryptography is a cornerstone of everyday digital security, where two parties must share a common key to communicate. The most common primitives in symmetric cryptography are stream ciphers and block ciphers that guarantee confidentiality of communications and hash functions for integrity. Thus, for securing our everyday life communication, it is necessary to be convinced by the security level provided by all the symmetric-key cryptographic primitives. The most important part of a stream cipher is the key stream generator, which provides the overall security for stream ciphers. Nonlinear Boolean functions were preferred for a long time to construct the key stream generator. In order to resist several known attacks, many requirements have been proposed on the Boolean functions. Attacks against the cryptosystems have forced deep research on Boolean function to allow us a more secure encryption. In this work we describe all main requirements for constructing of cryptographically significant Boolean functions. Moreover, we provide a construction of Boolean functions (semi-bent Boolean functions) which can be used in the construction of orthogonal variable spreading factor codes used in code division multiple access (CDMA) systems as well as in certain cryptographic applications.

1. Introduction

Cryptography has become a branch of information theory and is used within a mathematical approach to study the transmission of information from place to place. In a modern society, exchange and storage of information in an efficient, reliable, and secure manner are of fundamental importance. Applications of cryptography are present in many aspects of our society, and they include authentication and encryption (bank cards, wireless telephone, e-commerce), access control (car lock systems, ski lifts), and payment (prepaid telephone cards, e-cash). Behind all the previously mentioned applications, an underlying cryptographic system has to satisfy a number of security goals. Some important aspects in information security are data confidentiality, data integrity, authentication, and non-repudiation, and some of these goals will be elaborated later in the framework of Boolean functions. Therefore, cryptography is evermore important for business and industry as well as for society at large.

A classic example of a cryptosystem is depicted in Figure 1. Such a cryptosystem primitive is also called symmetric-key encryption algorithm, since the transmitted message (plaintext) is encrypted (into ciphertext) and decrypted with the same secret key which is shared between both sender and recipient. Symmetric cryptography is best introduced with an easy-to-understand problem: There are two users, Alice and Bob, who want to communicate over an insecure channel. The actual problem starts with the bad guy, Oscar, who has access to the channel, for instance, by hacking into an Internet router or by listening to the radio signals of a Wi-Fi communication. This type of unauthorized listening is called eavesdropping. Obviously, there are many situations in which Alice and Bob would prefer to communicate without Oscar listening. For instance, if Alice and Bob represent two offices of a car manufacturer, and they are transmitting documents containing the business strategy for the introduction of new car models in the next few years, these documents should not get into the hands of their competitors or of foreign intelligence agencies for that matter. In this situation, symmetric cryptography offers a powerful solution: Alice encrypts her message $m$ using a symmetric algorithm, yielding the ciphertext $c$ . Bob receives the ciphertext and decrypts the message. Decryption is, thus, the inverse process of encryption. What is the advantage? If we have a strong encryption algorithm, the ciphertext will look like random bits to Oscar and will contain no information whatsoever that is useful to him.

Figure 1.

Model of classic cryptosystem.

Symmetric-key cryptography comprises two large families of cryptographic primitives, namely, block and stream ciphers (see Figure 2). Since both block and stream ciphers provide significant performance improvement compared to public-key encryption techniques, they are commonly used as encryption schemes in practice. However, the design rules for these two primitives are quite different.

Figure 2.

Symmetric-key encryption schemes. (a) Stream cipher using algorithmic bit stream generator. (b) Block cipher.

In general, symmetric-key cryptography is much more computationally efficient than public-key cryptography (approximately 1000 faster), and it requires shorter key length to ensure the same level of security. On the other hand, every pair of users that wants to communicate using symmetric encryption must share a common secret key. If $n$ users want to ensure a pairwise secure communication, a total of $\frac{n\left(n-1\right)}{2}$ secret keys need to be exchanged, and every user must store and keep safe $n-1$ different secret keys, which is in many cases highly impractical. In comparison, public-key cryptography offers a functionality of only keeping a single private key secret.

The security of symmetric cryptosystems is strongly influenced by Boolean functions. They are often used as nonlinear combining functions in stream ciphers based on linear feedback shift register. Those functions allow making the relationship between the plaintext and the ciphertext as complex as possible. More precisely, a bit of the ciphertext is obtained from a bit of the plaintext by adding bitwise a key digit (the output of the Boolean function) whose dependence upon the LFSR entries (the secret information) is nonlinear. Thus, the security of such cryptosystems deeply relies on the choice of the Boolean function because the complexity of the relationship between the plaintext and the ciphertext depends entirely on the Boolean function. Indeed, some properties of the Boolean function can be exploited to gain access to the contents of encrypted messages, even if the key is unknown. Therefore, Boolean functions need to have some important characteristics that are called security criteria to resist several types of attacks (see Section 3). Furthermore, the research fields of Boolean functions regarding the cryptography include the design and implementation, the properties of Boolean functions, the construction and counting of Boolean functions with certain properties, the trade-off between different properties, and the properties according to new attacks.

A special class of Boolean functions defined as semi-bent function has been introduced in 1994, by scientists Chee, Lee, and Kim [1]. The motivation for their study is firstly related to their use in cryptography (in the design of cryptographic functions). Indeed, semi-bent functions can be balanced and resilient. They also possess various desirable characteristics such as low autocorrelation, a maximal nonlinearity among balanced plateaued functions, but they cannot have high algebraic degree. In terms of linear feedback shift-register synthesis, they are usually generated by certain power polynomials over a finite field and in addition are characterized by a low cross-correlation and high nonlinearity. Besides their practical use in cryptography, they are also widely used in code division multiple access (CDMA) communication systems for sequence design [2, 3]. In this context, families of maximum length linear feedback shift-register sequences having three-valued cross-correlation are used. Such sequences have received a lot of attention since the late 1960s and can be generated by a semi-bent function. Even though a lot of work has been done on semi-bent functions, there are a few generic methods of constructing semi-bent functions that can be found in the literature. The classification of these functions is still elusive, especially their construction are challenging problems. Some open problems and an overview of the known construction related on semi-bent functions can be found in the book of Mesnager [4]. The rest of this chapter is organized as follows. In Section 2 the essential background on Boolean functions is given. Some main requirements for constructing significant Boolean function are given in Section 3. An infinity class of semi-bent function specified by employing some sufficient conditions is given in Section 4. Some concluding remarks are given in Section 5.

2. Useful definitions and terms

Let ${\mathbb{F}}_2^n$ denote the $n$ -dimensional vector space over the prime field ${\mathbb{F}}_2$ . Let $x=\left(x_1,\dots ,x_n\right)$ be a vector over ${\mathbb{F}}_2$ of length $n$ .

A Boolean function $f\left(x_1,\dots ,x_n\right)$ in $n$ -variables is an arbitrary function from ${\mathbb{F}}_2^n$ to ${\mathbb{F}}_2$ . It can also be interpreted as the output column of its truth table, i.e., a binary string of length $2^n$ ,

$$f=\left[f\left(0,0,\dots ,0\right),f\left(1,0,\dots ,0\right),\dots ,f\left(1,1,\dots ,1\right)\right].$$ E1

An $n$ -variable function $f$ is said to be balanced if its output column in the truth table contains equal number of 1’s and 0’s.

Any Boolean function has a unique representation as a multivariate polynomial over Galois field of two elements, called algebraic normal form (ANF),

$$f\left(x_1,\dots ,x_n\right)=a_0+\sum _{1\le i\le n}{a}_i{x}_i+\sum _{1\le i<j\le n}{a}_{\mathit{ij}}{x}_i{x}_j+\dots +a_{12\dots n}{x}_1{x}_2\dots x_n$$ E2

where the coefficients $a_0,a_{\mathit{ij}},\dots ,a_{12\dots n}$ belong to $\left\{0,1\right\}$ .

The algebraic degree, denoted by $\text{deg}\left(f\right)$ , is the number of variables in the highest order monomial with nonzero coefficient. A Boolean function with $\text{deg}\left(f\right)\le 1$ is said to be affine, and the set of all $n$ -variable affine functions is denoted by ${\mathcal{A}}_n$ . An affine function with the constant term equal to zero is called a linear function.

The nonlinearity of an $n$ -variable function $f$ is $N_f=\underset{g\in {\mathcal{A}}_n}{\text{min}}d\left(f,g\right)$ , which measures the minimum distance between $f$ and all $n$ -variable affine functions.

Many properties of Boolean function can be deduced from its Walsh spectra. The Walsh transform of $f\left(x\right)$ in point $\omega \in {\mathbb{F}}_2^n$ is an integer-valued function over ${\mathbb{F}}_2^n$ defined by

$$W_f\left(\omega \right)=\sum _{x\in {\mathbb{F}}_2^n}{\left(-1\right)}^{f\left(x\right)+x·\omega },$$ E3

where $x·\omega =x_1{\omega }_1+\dots +x_n{\omega }_n$ is the inner product of two vectors over ${\mathbb{F}}_2^n$ . The set { $W_f\left(\omega \right):\omega \in {\mathbb{F}}_2^n\}$ is called the Walsh spectrum of $f$ .

A Boolean function $f\left(x\right)$ is called plateaued if its Walsh spectrum only takes three values, $0$ and $\pm 2^{\lambda }$ , where $\lambda$ is some positive integer.

Two Boolean functions $f\left(x\right),g\left(x\right)$ are said to be a pair of disjoint spectra functions if

$$W_f\left(\omega \right)·W_g\left(\omega \right)=0.$$ E4

$\text{for}\mathrm{all}\omega \in {\mathbb{F}}_2^n.$

In terms of Walsh spectra, the nonlinearity of $f$ is given by

$$N_f=2^{n-1}-\frac{1}{2}\underset{\omega \in {\mathbb{F}}_2^n}{\text{max}}\left|W_f\left(\omega \right)\right|.$$ E5

A function is balanced if and only if $W_f\left(0\right)=0$ , i.e., $\#\left\{x\left|f\left(x\right)=0\right.\right\}=\#\left\{x\left|f\left(x\right)=1\right.\right\}$ .

An $n$ -variable Boolean function $f$ is said to be bent if its Walsh transform takes only two values $\pm 2^{\frac{n}{2}}$ . Moreover, $f$ is said to be semi-bent function if for all $\omega \in {\mathbb{F}}_2^n$

$$W_f\left(\omega \right)\in \left\{\begin{array}{l}\left\{0,\pm 2^{\frac{n+1}{2}}\right\},\mathit{\text{if}}n\mathit{\text{is}}\mathit{odd}\hfill \\ \left\{0,\pm 2^{\frac{n+2}{2}}\right\},\mathit{\text{if}}n\mathit{\text{is even}}\end{array}\right..$$ E6

The derivative of $f\left(x\right)$ at $a\in {\mathbb{F}}_2^n$ , denoted by $D_{a}f\left(x\right)$ , is a Boolean function defined by $D_{a}f\left(x\right)=f\left(x+a\right)+f\left(x\right)$ , for all $x\in {\mathbb{F}}_2^n$ . The notion of the derivative of a Boolean function is extended to higher orders as follows.

Suppose $\left\{a_1,\dots ,a_k\right\}$ is a basis of a $k$ dimensional subspace $V$ of ${\mathbb{F}}_2^n$ . The $k$ -th derivative of $f$ with respect to $V$ , denoted by $D_{V}f\left(x\right)$ , is a Boolean function defined by

$$D_{V}f\left(x\right)=D_{a_k}{D}_{a_{k-1}}\dots D_{a_1}f\left(x\right),$$ E7

$\text{for}\mathrm{all}x\in {\mathbb{F}}_2^n.$

3. Cryptographic requirements for constructing Boolean functions

One of the fundamental research topics in cryptography is the construction of cryptographically significant Boolean functions, that is, a function which possesses some of the following properties:

1. High algebraic degree aims to increase the linear complexity in ciphers. Using Boolean functions of high degree in block ciphers leads to more complicated systems of equations describing the cipher and hence makes cryptanalysis of the cipher more difficult. All cryptosystems using Boolean functions for confusion can be attacked if the functions have relatively low algebraic degree, i.e., the Berlekamp-Massey attack [5] or the Ronjom-Helleseth attack [6] can be applied. Note that the algebraic degree of a Boolean function in $n$ -variables is at most $n$ .

2. In order to prevent the system from leaking statistical dependence between the input and output, the concept of balancedness implies that a given Boolean function outputs equally many zeros and ones over all possible input values. To avoid distinguishing attacks [7], cryptographic function must be balanced. Note that the algebraic degree of a Boolean balanced function in $n$ -variables is at most $n-1$ .

3. High nonlinearity is one of the most important properties in the design of symmetric-key cryptosystems, since it directly affects the resistance of the cipher to majority of cryptanalytic techniques. The nonlinearity simply measures the Hamming distance to the set of all affine functions. Therefore, a high nonlinearity implies a better resistance to affine approximation attacks [8]. According to the definition of nonlinearity, all affine functions have zero nonlinearity. On the other hand, a Boolean function having nonzero nonlinearity implies the function is not affine. Thus, the nonlinearity of a nonlinear Boolean function cannot exceed $2^{n-1}$ . On an even size Boolean space, there is a class of Boolean functions, called bent functions, that have maximum nonlinearity ( $2^{n-1}-2^{\frac{n}{2}-1}$ ). In general, it is not an easy problem to identify all Boolean functions with high nonlinearity. However, this problem has been completely solved for quadratic Boolean functions (Boolean functions with the algebraic degree 2).

4. In order to avoid correlation attack [9], the concept of correlation immune of order m implies that any sub-function deduced from a given Boolean function by fixing at most $m$ inputs has the same output distribution as a given Boolean function. Correlation immune has long been recognized as one of the critical indicators of nonlinear combining functions of shift registers in stream generators. Moreover, if a balanced Boolean function $f$ is correlation immune of order $m$ , then f is said to be m-resilient. When used in stream cipher systems, a Boolean function is required to have high nonlinearity and resiliency for protection against correlation attacks. It is actually very difficult to find a balanced Boolean function which has a high correlation immunity order and at the same time has a high nonlinearity.

5. Optimal algebraic immunity aims to provide resistance against algebraic attack. The algebraic immunity is the minimum value of $d$ such that a given Boolean function $f$ or its complement $1+f$ admits an annihilator (a nonzero Boolean function $g$ such that $\mathit{fg}=0$ ) of algebraic degree $d$ . In ciphers, Boolean functions with high algebraic immunity should be used in order to avoid the application of algebraic cryptanalysis [10]. Recall that algebraic attacks recover the secret key, or at least the initialization of the system, by solving a system of multivariate algebraic equations that describes a cipher. Although a high algebraic immunity is the necessary cryptographic requirement, it is not sufficient, because of a more general kind of attack introduced by Courtois [11] in 2003 called fast algebraic attack. It is well-known that maximum algebraic immunity of $n$ -variable Boolean function is $⌈\frac{n}{2}⌉$ . The problem of efficiently constructing balanced Boolean functions with optimal algebraic immunity is thus of great significance. Moreover, several examples of functions having optimal algebraic immunity could be found but no example of correlation immune Boolean function with optimal algebraic immunity.

However, the major problem in construction of cryptographically strong functions is that the multiple criteria mentioned above have to be satisfied at the same time, while there exist intrinsic trade-offs between them. Such properties allow the system designer to quantify the level of resistance of the system to attacks. Since the number of Boolean functions in $n$ -variables is $2^{2^n}$ , an exhaustive search of functions which satisfy some of the properties above is practically impossible (unless the input variable space $n$ is quite small). Indeed, the difficulty precisely lies in finding the best trade-offs between all criteria and proposing concrete constructions of functions achieving them. Thus, bringing new construction methods of these functions is still a vivid research activity.

By $\left(n,m,d,N_f\right)$ function we specify an $n$ -variable, $m$ -resilient Boolean function $f$ , algebraic degree $d$ , and nonlinearity $N_f$ . Siegenthaler [9] proved that $m+d\le n+1$ if $m\le n-2$ . The exact nature of trade-offs among order of correlation immunity, nonlinearity, and algebraic degree has also been investigated, for instance, ([12, 13]. Using the above bounds, one may naturally try to provide the construction of an $\left(n,m,d,N_f\right)$ function for any given $n$ and $m$ while at the same time attempting to optimize $d$ and $N_f$ . This optimization can be efficiently done for a small number of variables $n\le 5$ , but even some interesting open problems for $n>5$ , related to the existence of $\left(8,1,6,116\right)$ and $\left(7,2,4,56\right)$ functions, were settled using some sophisticated computer search and theoretical results [14]. The importance of finding these optimized functions in small number of variables lies in the fact that one can use these functions recursively to obtain new instances of optimal functions in larger number of variables. For instance, Tarannikov [15] has provided a construction technique of optimized resilient Boolean functions with maximum possible nonlinearity. Basically Tarannikov’s construction is a recursive one, and using this technique and taking an $\left(n,m,d,N_f\right)$ optimized function, such as the $\left(7,2,4,56\right)$ function, one can generate a sequence of optimal plateaued $\left(7+3i,2+2i,4+i,2^{7+3i-1}-2^{2+2i+1}\right)$ functions, $\left(10,4,5,480\right),\left(13,6,6,3968\right),\left(16,8,7,32256\right),\mathit{etc}.$ A modified version of Tarannikov’s construction was presented in [16]. A construction of Boolean functions with maximum nonlinearity and small order of resiliency has also been considered in [17]. Later, Carlet [18] proposed a general framework for these iterative concatenation methods, unifying most of these techniques into a single method called “indirect sum.” This construction leads to a multiple branching infinite tree of functions, but in order to employ this construction in the design of optimal plateaued functions in an iterative manner, there are certain conditions imposed on the initial pairs of disjoint spectra functions.

A recursive construction method of optimal plateaued functions (the functions of the form $\left(n,m,n-m-1,2^{n-1}-2^{m+1}\right)$ and for $m>\frac{n}{2}-2$ ) is given in [19]. The iteration once again employs a $\left(7,2,4,56\right)$ function, whose 6-variable sub-functions have disjoint spectra, to construct a sequence of $\left(7+4i,2+3i,4+i,2^{7+4i-1}-2^{2+3i+1}\right)$ optimal plateaued functions (whose $\left(7+4i-1\right)$ -variable sub-functions are again disjoint spectra functions). Nevertheless, this iterative method generates the functions with relatively large order of resiliency ( $\left(11,5,5,964\right),\left(15,8,6,15872\right),\left(19,11,7,258048\right),\mathit{etc}.$ ), and in addition it only gives one infinite sequence of optimal plateaued functions. For instance, in the first step of iteration, an optimal plateaued $\left(11,5,5,964\right)$ function is generated whose $10$ -variable sub-functions are again disjoint spectra functions (two $\left(10,5,4,452\right)$ disjoint spectra functions), thus leaving some open slots concerning the construction of optimal plateaued functions when $n=8,9,10$ . On the other hand, a modified Tarannikov construction has a slightly different effect, since the resiliency is increased by two at each step of iteration (but the degree is also increased by one) and the iteration step is three instead of four. Still, optimal plateaued functions cannot be generated for $n=8$ or $n=9$ using the particular $\left(7,2,4,56\right)$ function.

The idea of employing a set of disjoint spectra functions in construction of highly nonlinear resilient functions was firstly elaborated in [16]. Later, the sets of disjoint spectra functions were successfully used in constructions of almost optimal resilient functions. The generalized Maiorana-McFarland (GMM) construction method for obtaining the almost optimal resilient functions has been proposed in [20]. Namely, this construction generates the functions with relatively large number of variables and small order of resiliency. The resulting functions cannot be viewed as a pair of disjoint spectra almost optimal resilient functions. Recently, Zhang and Pasalic used GMM technique to obtain the strictly optimal resilient functions with high nonlinearity and good algebraic properties [21]. The design of some balanced functions that also achieve currently best known nonlinearity can be found in [22]. Although these construction methods achieve currently the best nonlinearity for a given function, these methods are only efficient for relatively large input space of variables.

4. A construction of semi-bent Boolean functions

As it is described in the previous section, in the design of cryptographic functions, there is a need to consider various nonlinear characteristics simultaneously. But some characteristics restrict each other. Bent functions, for example, have maximum nonlinearity and satisfy the propagation criteria with respect to every nonzero vector over the Boolean spaces on which they are defined. However, bent functions are not balanced and exist only on even size Boolean spaces. Furthermore, bent functions are not correlation immune, and they are not suitable for use in cryptosystems. Partially bent functions are highly nonlinear and can be balanced. However, except for bent functions, partially bent functions have nonzero linear structures that are cryptographically undesirable. For these reasons, people study other classes of Boolean functions to try to overcome the disadvantage of bent functions or partially bent functions. The class of plateaued Boolean functions is one candidate that is defined by a series of inequalities and examines the critical case of each inequality. Compared with other functions, plateaued functions may reach the upper bound on nonlinearity given by the inequalities.

In what follows we specify a simple generic method for deriving semi-bent functions. This method is deduced from two bent functions whose derivatives differ by a constant one. It should be noticed that there are strong connections behind the concepts of bentness and semi-bentness though many questions remain unanswered. In particular, it is not settled how the cardinality of the whole class of bent functions relates to the class of semi-bent functions. Most notably, it appears that certain classes of semi-bent functions derived in [23] defined for even $n$ are not extendable to bent functions in $n+2$ variables. In [24] and recently in [25], a sufficient condition on two bent functions $g$ and $h$ used in the construction of semi-bent functions was given as the following theorem.

Theorem 1. Let n be even, and suppose that f and g are two bent Boolean functions in n-variables. If there exists an $a\in {\mathbb{F}}_2^n$ such that $D_{a}f\left(x\right)=D_{a}g\left(x\right)+1$ , then the function

$$h\left(x\right)=f\left(x\right)+g\left(x\right)+D_{a}f\left(x\right)+D_a\left[f\left(x\right)g\left(x\right)\right]$$ E8

is a semi-bent function in even number of variables.

This condition immediately implies the possibility of constructing infinite classes of semi-bent functions using known classes of quadratic bent functions. Notice that all quadratic Boolean functions (including bent and semi-bent functions) are classified up to equivalence and any quadratic bent function is affine equivalent to the canonical form given by $\sum _{i=1}^{n/2}{x}_{2i-1}{x}_{2i}$ .

One may define a Boolean function f with $n$ even to be a quadratic bent function of the form $f\left(x\right)=\sum _{i=1}^n{b}_i{x}_i+\sum _{1\le i<j\le n}{c}_{i,j}{x}_i{x}_j$ for suitably chosen $b_i,c_{i,j}\in {\mathbb{F}}_2$ . Furthermore, let $g$ be a Boolean function defined as $g\left(x\right)=f\left(x\right)+\sum _{i=1}^n{\alpha }_i{x}_i$ , where ${\alpha }_i\in {\mathbb{F}}_2$ . Then, if $a\in {\mathbb{F}}_2^n$ is such that $a·\alpha =1$ , it can be shown that the function

$$h\left(x\right)=f\left(x\right)+g\left(x\right)+D_{a}f\left(x\right)+D_a\left[f\left(x\right)g\left(x\right)\right]$$

is a quadratic semi-bent Boolean function.

Another related approach, though without restriction on the degree of a single bent function used, is given by the following result.

Theorem 2. Let $f$ be bent Boolean function in even number of variables. For $a,\alpha \in {\mathbb{F}}_2^n$ such that $a·\alpha =1$ define the function $g$ as either

$$g\left(x\right)=\left\{\begin{array}{l}f\left(x\right)+\alpha ·x+d\\ f\left(x+a\right)+\alpha ·x+d\end{array}\right.,$$ E9

where $d\in {\mathbb{F}}_2$ . Then, the function

$$h\left(x\right)=f\left(x\right)+g\left(x\right)+D_{a}f\left(x\right)+D_a\left[f\left(x\right)g\left(x\right)\right]$$

is a semi-bent function.

Proof. Obviously, in both cases $g$ is also a bent function, and if $g\left(x\right)=f\left(x\right)+\mathit{\alpha x}+d$ , we have

$$D_{a}f\left(x\right)+D_{a}g\left(x\right)=\left[f\left(x\right)+f\left(x+a\right)\right]+\left[g\left(x\right)+g\left(x+a\right)\right]$$

$$=\left[f\left(x\right)+f\left(x+a\right)\right]+\left[f\left(x\right)+\mathit{\alpha x}+d+f\left(x+a\right)+\mathit{\alpha x}+\mathit{a\alpha }+d\right]$$

$$=a·\alpha =1.$$

A similar calculation gives that

$$D_{a}f\left(x\right)+D_{a}g\left(x\right)=1\text{if}g\left(x\right)=f\left(x+a\right)+\mathit{\alpha x}+d.$$

By Theorem 1 we deduce that $h\left(x\right)=f\left(x\right)+g\left(x\right)+D_{a}f\left(x\right)+D_a\left[f\left(x\right)g\left(x\right)\right]$ is a semi-bent function. q.e.d.

This result enables us to construct, for even $n$ , an infinite sequence of semi-bent functions from bent functions. It would be of interest to find other examples or classes of bent functions $g_1$ , $g_2$ , apart from using affine equivalent functions $g_1$ and $g_2$ , satisfying $D_a{g}_1\left(x\right)=D_a{g}_2\left(x\right)+1$ . This appears to be a nontrivial task since apart from establishing the fact that the used bent functions are indeed affine inequivalent, at the same time, their derivatives need to satisfy the condition in Theorem 1.

Example 1. Let $f\left(x_1,x_2,x_3,x_4,x_5,x_6\right)=x_1{x}_3{x}_4+x_2{x}_3{x}_4+x_1{x}_5{x}_6+x_2{x}_5{x}_6+x_1{x}_2+x_3{x}_5+x_4{x}_6+x_5{x}_6$ be a bent function of degree 3 over ${\mathbb{F}}_2^6$ . Take $a=\left(0,0,1,0,0,0\right)$ and $\alpha =\left(1,0,1,0,0,0\right)$ such that $a·\alpha =1$ . Define the function $g$ as either

$$g\left(x\right)=\left\{\begin{array}{c}f\left(x\right)+x_1+x_3\\ f\left(x+a\right)+x_1+x_3\end{array}\right.=\left\{\begin{array}{c}f\left(x\right)+x_1+x_3\\ f\left(x\right)+x_1{x}_4+x_2{x}_4+x_1+x_3+x_5\end{array}\right.,$$

where $d=0\in {\mathbb{F}}_2$ .

Let us take $g\left(x\right)=f\left(x\right)+x_1+x_3$ . We have

$$D_{a}f\left(x\right)=f\left(x\right)+f\left(x+a\right)=f\left(x\right)+f\left(x\right)+x_1{x}_4+x_2{x}_4+x_5=x_1{x}_4+x_2{x}_4+x_5,$$

so that

$$f\left(x\right)+g\left(x\right)+D_{a}f\left(x\right)=x_1{x}_4+x_2{x}_4+x_1+x_3+x_5.$$

Then, using the idempotent property of Boolean ring,

$$f\left(x\right)g\left(x\right)=f\left(x\right)\left(f\left(x\right)+x_1+x_3\right)=f\left(x\right)\left(1+x_1+x_3\right)$$

$$=\left(x_1{x}_3{x}_4+x_2{x}_3{x}_4+x_1{x}_5{x}_6+x_2{x}_5{x}_6+x_1{x}_2+x_3{x}_5+x_4{x}_6+x_5{x}_6\right)\left(1+x_1+x_5\right)$$

$$=x_1{x}_2{x}_3{x}_4+x_1{x}_2{x}_5{x}_6+x_2{x}_3{x}_4{x}_5+x_1{x}_2{x}_5+x_1{x}_3{x}_4+x_1{x}_3{x}_5+x_1{x}_4{x}_6$$

$$+x_2{x}_3{x}_4+x_4{x}_5{x}_6+x_4{x}_6.$$

$$f\left(x+a\right)g\left(x+a\right)=f\left(x+a\right)\left(f\left(x+a\right)+x_1+x_3+1\right)=f\left(x+a\right)\left(x_1+x_3\right)$$

$$=\left(f\left(x\right)+x_1{x}_4+x_2{x}_4+x_5\right)\left(x_1+x_3\right)$$

$$=f\left(x\right)\left(x_1+x_3\right)+\left(x_1{x}_4+x_2{x}_4+x_5\right)\left(x_1+x_3\right).$$

After some simplification, we get

$$D_a\left[f\left(x\right)g\left(x\right)\right]=f\left(x\right)g\left(x\right)+f\left(x+a\right)g\left(x+a\right)$$

$$=f\left(x\right)+\left(x_1{x}_4+x_2{x}_4+x_5\right)\left(x_1+x_3\right)$$

$$=x_1{x}_5{x}_6+x_2{x}_5{x}_6+x_1{x}_2+x_1{x}_4+x_1{x}_5+x_2{x}_4+x_4{x}_6+x_5{x}_6.$$

Finally,

$$h\left(x\right)=f\left(x\right)+g\left(x\right)+D_{a}f\left(x\right)+D_a\left[f\left(x\right)g\left(x\right)\right]$$

$$=x_1{x}_5{x}_6+x_2{x}_5{x}_6+x_1{x}_2+x_1{x}_5+x_4{x}_6+x_5{x}_6+x_1+x_3+x_5.$$

It is easy to compute the Walsh spectrum of function $h\left(x\right)$ , i.e., $W_h\left(\omega \right)=\left\{0,\pm 16\right\}$ , which means that $h\left(x\right)$ is a semi-bent function.

Notice that the standard derivation rule for multiplication does not apply for our definition of derivatives. Indeed, the derivative $D_a\left[f\left(x\right)g\left(x\right)\right]=f\left(x\right)g\left(x\right)+f\left(x+a\right)g\left(x+a\right)$ is different from $g\left(x\right)D_{a}f\left(x\right)+f\left(x\right)D_{a}g\left(x\right)=f\left(x+a\right)g\left(x\right)+f\left(x\right)g\left(x+a\right).$ Furthermore, using the fact that $D_a{D}_{a}f\left(x\right)=0$ for any Boolean function $f$ , we have

$$D_{a}h\left(x\right)=h\left(x\right)+h\left(x+a\right)$$

$$=f\left(x\right)+g\left(x\right)+D_{a}f\left(x\right)+D_a\left[f\left(x\right)g\left(x\right)\right]+f\left(x+a\right)+g\left(x+a\right)+D_{a}f\left(x+a\right)+D_a\left[f\left(x+a\right)g\left(x+a\right)\right]$$

$$=D_{a}f\left(x\right)+D_{a}g\left(x\right)+D_a{D}_{a}f\left(x\right)+D_a{D}_a\left[f\left(x\right)g\left(x\right)\right]$$

$$=D_{a}f\left(x\right)+D_{a}g\left(x\right)=1.$$

Thus, the element $a$ is always a linear structure of $h\left(x\right)$ . Nevertheless, we show that under certain sufficient conditions, $a$ is the only linear structure of $h\left(x\right)$ . We have the following theorem.

Theorem 3. Let $h$ be defined as in Theorem 2, and assume that a bent function $f\left(x\right)$ is such that $\text{deg}\left(D_{b}f\left(x\right)\right)>1$ , for any $b\in {\mathbb{F}}_2^n\setminus \left\{0\right\}.$ Then $h$ has a single linear structure, that is, $D_{b}h\left(x\right)=h\left(x\right)+h\left(x+b\right)$ is a constant function only for $b=a$ .

Proof. Assume that $g\left(x\right)=f\left(x+a\right)+\mathit{\alpha x}+d$ . Without loss of generality, we can take $d=0.$ Then,

$$D_{b}f\left(x\right)+D_{b}g\left(x\right)=\left[f\left(x\right)+f\left(x+b\right)\right]+\left[g\left(x\right)+g\left(x+b\right)\right]$$

$$=\left[f\left(x\right)+f\left(x+b\right)\right]+\left[f\left(x+a\right)+\alpha \left(x+a\right)+d+f\left(x+a+b\right)+\alpha \left(x+a+b\right)+d\right]$$

$$=D_b{D}_{a}f\left(x\right)+\mathit{\alpha b},$$

where $D_b{D}_{a}f\left(x\right)=f\left(x\right)+f\left(x+a\right)+f\left(x+b\right)+f\left(x+a+b\right)$ , and therefore

$$D_{b}h\left(x\right)=D_b{D}_{a}f\left(x\right)+\mathit{\alpha b}+D_b{D}_{a}f\left(x\right)+D_b{D}_a\left[f\left(x\right)g\left(x\right)\right]=D_b{D}_a\left[f\left(x\right)g\left(x\right)\right]+\mathit{\alpha b}.$$

Hence, $D_{b}h\left(x\right)$ is constant if and only if $D_b{D}_a\left[f\left(x\right)g\left(x\right)\right]$ is constant. But,

$$D_b{D}_a\left[f\left(x\right)g\left(x\right)\right]=D_b\left[f\left(x\right)g\left(x\right)+f\left(x+a\right)g\left(x+a\right)\right]$$

$$=D_b\left[f\left(x\right)\left(f\left(x+a\right)+\mathit{\alpha x}\right)+f\left(x+a\right)\left(f\left(x\right)+\alpha \left(x+a\right)\right)\right]$$

$$=D_b\left[\mathit{\alpha x}\left(f\left(x\right)+f\left(x+a\right)\right)+\mathit{\alpha af}\left(x+a\right)\right]$$

$$=D_b\left[\mathit{\alpha x}\left(f\left(x\right)+f\left(x+a\right)\right)+f\left(x+a\right)\right]$$

$$={\mathit{\alpha xD}}_b{D}_{a}f\left(x\right)+\mathit{\alpha b}\left[f\left(x+b\right)+f\left(x+a+b\right)\right]+f\left(x+a\right)+f\left(x+a+b\right).$$

Thus, if $\mathit{\alpha b}=0$ , then $D_{b}h\left(x\right)$ is constant if and only if

$${\mathit{\alpha xD}}_b{D}_{a}f\left(x\right)=f\left(x+a\right)+f\left(x+a+b\right)$$

$$\mathit{\alpha x}\left[f\left(x\right)+f\left(x+a\right)+f\left(x+b\right)+f\left(x+a+b\right)\right]=f\left(x+a\right)+f\left(x+a+b\right)$$

$$\left(\mathit{\alpha x}+1\right)\left[f\left(x+a\right)+f\left(x+a+b\right)\right]+\mathit{\alpha x}\left[f\left(x\right)+f\left(x+b\right)\right]=0$$

$$\left(\mathit{\alpha x}+1\right)D_{b}f\left(x+a\right)+\mathit{\alpha x}{D}_{b}f\left(x\right)=0$$

$$\mathit{\alpha x}{D}_{b}f\left(x+a\right)+\mathit{\alpha x}{D}_{b}f\left(x\right)+D_{b}f\left(x+a\right)=0.$$

There are four possible cases:

1. $\mathit{\alpha x}{D}_{b}f\left(x+a\right)=\mathit{\alpha x}{D}_{b}f\left(x\right)=D_{b}f\left(x+a\right)=0$ , i.e., $D_{b}f\left(x+a\right)=0\iff f\left(x+a\right)=f\left(x+a+b\right)\Rightarrow b=0.$ A contradiction.

2. $\mathit{\alpha x}{D}_{b}f\left(x+a\right)=\mathit{\alpha x}{D}_{b}f\left(x\right)=1\wedge D_{b}f\left(x+a\right)=0$ , i.e., $D_{b}f\left(x+a\right)=0\Rightarrow b=0.$ A contradiction.

3. $\mathit{\alpha x}{D}_{b}f\left(x+a\right)=0\wedge \mathit{\alpha x}{D}_{b}f\left(x\right)=D_{b}f\left(x+a\right)=1$ , i.e., $D_{b}f\left(x+a\right)=0\Rightarrow b=0.$ A contradiction.

4. $\mathit{\alpha x}{D}_{b}f\left(x+a\right)=D_{b}f\left(x+a\right)=1\wedge \mathit{\alpha x}{D}_{b}f\left(x\right)=0$ , i.e., $D_{b}f\left(x+a\right)=0\Rightarrow b=0.$ A contradiction.

On the other hand, if $\mathit{\alpha b}=1$ , then $D_{b}h\left(x\right)$ is constant if and only if

$${\mathit{\alpha xD}}_b{D}_{a}f\left(x\right)=f\left(x+a\right)+f\left(x+b\right)$$

$$\mathit{\alpha x}\left[f\left(x\right)+f\left(x+a\right)+f\left(x+b\right)+f\left(x+a+b\right)\right]=f\left(x+a\right)+f\left(x+b\right)$$

$$\left(\mathit{\alpha x}+1\right)\left[f\left(x+a\right)+f\left(x+b\right)\right]+\mathit{\alpha x}\left[f\left(x\right)+f\left(x+a+b\right)\right]=0.$$

It is obvious that $f\left(x+a\right)=f\left(x+b\right)$ is equivalent to $f\left(x\right)=f\left(x+a+b\right)$ . Thus, the above equation is constant if and only if $f\left(x+a\right)=f\left(x+b\right)$ , which implies that $a=b$ . The sufficiency of this condition is obvious. For the necessity, we first observe that for $a\ne b$ the functions $f\left(x+a\right)+f\left(x+b\right)$ and $f\left(x\right)+f\left(x+a+b\right)$ being derivatives of a bent function $f$ are both nonconstant. Then, assuming that

$$D_b{D}_{a}f\left(x\right)=f\left(x\right)+f\left(x+a\right)+f\left(x+b\right)+f\left(x+a+b\right)=0,$$

it would imply that $f\left(x+a\right)+f\left(x+b\right)$ is constant, a contradiction. On the other hand, the function ${\mathit{\alpha xD}}_b{D}_{a}f\left(x\right)$ cannot be balanced, unless $D_b{D}_{a}f\left(x\right)=\mathit{\alpha x}$ . Because of the assumption, $\text{deg}\left(f\left(x+a\right)+f\left(x+b\right)\right)>1$ and therefore cannot be equal to αx.

The proof for the case $g\left(x\right)=f\left(x\right)+\mathit{\alpha x}+d$ is similar as above, and it is omitted here. q.e.d.

Notice the condition in Theorem 3 that $\text{deg}\left(D_{b}f\left(x\right)\right)>1$ is sufficient but may not be necessary. An analysis of other cryptographic criteria appears to be difficult due to the dependency of $h$ on the choice of a bent function $f$ and the use of the derivative $D_a\left[f\left(x\right)g\left(x\right)\right]$ in its definition, which is illustrated in the following example.

Example 2. Let $n$ be even and $f\left(x,y\right)=x·y$ , where $x,y\in {\mathbb{F}}_2^k$ is a bent function and belongs to the Maiorana-McFarland class. Then, defining $g\left(x,y\right)=f\left(x+a,y+b\right)+\left(\alpha ,\beta \right)·\left(x,y\right)$ for a nonzero $\left(a,b\right)\in {\mathbb{F}}_2^k\times {\mathbb{F}}_2^k$ such that $\left(\alpha ,\beta \right)·\left(a,b\right)=1$ , we have

$$g\left(x,y\right)=x·y+\left(\alpha +b\right)·x+\left(a+\beta \right)·y+a·b,$$

which is clearly a bent function obtained by adding an affine function to $f$ . Similarly,

$D_{\left(a,b\right)}f\left(x,y\right)=x·b+a·y+a·b$ , so that

$$f\left(x,y\right)+g\left(x,y\right)+D_{\left(a,b\right)}f\left(x,y\right)=\alpha ·x+\beta ·y.$$

Then, using the idempotent property of Boolean ring,

$$f\left(x,y\right)·g\left(x,y\right)=\left(x·y\right)\left(x·y+\left(\alpha +b\right)·x+\left(a+\beta \right)·y+a·b\right)$$

$$=\left(1+a·b\right)\left(x,y\right)+\left(\left(\alpha +b\right)·x+\left(a+\beta \right)·y\right)\left(x·y\right).$$

Note that the first term is a quadratic function and the second term is cubic. After some simplifications we have

$$D_{\left(a,b\right)}\left[f\left(x,y\right)g\left(x,y\right)\right]=x·y+\left(b·x+a·y+a·b\right)(1+a·b+\alpha ·x+\alpha ·a+b·x$$

$$+a·b+a·y+\beta ·y+\beta ·b)$$

$$=x·y+\left(b·x+a·y+a·b\right)\left(\alpha ·x+b·x+a·y+\beta ·y+a·b+\beta ·b\right)$$

$$=x·y+\left(b·x+a·y+a·b\right)\left(\left(\alpha +b\right)·x+\left(\beta +a\right)·y+a·b+\beta ·b\right).$$

Finally,

$$h\left(x,y\right)=f\left(x,y\right)+g\left(x,y\right)+D_{\left(a,b\right)}f\left(x,y\right)+D_{\left(a,b\right)}\left[f\left(x,y\right)g\left(x,y\right)\right]$$

$$=x·y+\left(\alpha ·x+\beta ·y\right)\left(b·x+a·y+a·b+1\right)+\left(b·x+a·y+a·b\right)\left(1+\beta ·b\right).$$

More precisely, it can be illustrated using Example 1.

Example 3. Let $f\left(x_1,x_2,x_3,x_4,x_5,x_6\right)=x_1{x}_3{x}_4+x_2{x}_3{x}_4+x_1{x}_5{x}_6+x_2{x}_5{x}_6+x_1{x}_2+x_3{x}_5+x_4{x}_6+x_5{x}_6$ be a bent function of degree 3 over ${\mathbb{F}}_2^6$ . Take $a=\left(0,0,1,0,0,0\right)$ and $\alpha =\left(1,0,1,0,0,0\right)$ such that $a·\alpha =1$ . Define the function $g$ as $g\left(x\right)=f\left(x\right)+x_1+x_3.$ By Example 1 we have

$$h\left(x\right)=x_1{x}_5{x}_6+x_2{x}_5{x}_6+x_1{x}_2+x_1{x}_5+x_4{x}_6+x_5{x}_6+x_1+x_3+x_5.$$

Moreover, by Theorem 2 $h$ has a single linear structure only for $b=a$ . Indeed,

$$D_{a}h\left(x\right)=h\left(x\right)+h\left(x+a\right)$$

$$=x_1{x}_5{x}_6+x_2{x}_5{x}_6+x_1{x}_2+x_1{x}_5+x_4{x}_6+x_5{x}_6+x_1+x_3+x_5+$$

$$+x_1{x}_5{x}_6+x_2{x}_5{x}_6+x_1{x}_2+x_1{x}_5+x_4{x}_6+x_5{x}_6+x_1+x_3+1+x_5$$

$$=1.$$

5. Conclusions

The need for the most possible secure cryptographic primitives in cipher systems is of great importance. In the case of stream ciphers, most of the reliability and security lies in the Boolean functions. For the cryptographic point of view to be good, a Boolean function should possess several cryptographic properties mentioned in this work. Very often such properties contradict each other. Therefore, the problem of constructing Boolean functions with stronger cryptographic properties is still a vivid research activity. We may also require new properties because attacks never stop. On the other hand, semi-bent functions are interesting for defending against the so-called soft output joint attack on pseudorandom generators, which are used in the IS-95 standard of code division multiple access technology. In this work we present an infinite sequence of semi-bent functions using known classes of quadratic bent functions. The construction of other classes of infinite sequences of semi-bent functions is an interesting research challenge.

Acknowledgments

This research was supported by the Slovenian Research Agency (research program P2-0037).