Open access peer-reviewed chapter

Implementing Symmetric Cryptography Using Sequence of Semi-Bent Functions

By Samed Bajrić

Submitted: December 3rd 2018Reviewed: February 7th 2019Published: May 10th 2019

DOI: 10.5772/intechopen.85023

Downloaded: 115

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.

Keywords

  • symmetric cryptography
  • Boolean functions
  • Walsh spectrum
  • nonlinearity
  • resiliency
  • (fast) algebraic attack

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 musing 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 nusers want to ensure a pairwise secure communication, a total of nn12secret keys need to be exchanged, and every user must store and keep safe n1different 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 F2ndenote the n-dimensional vector space over the prime field F2. Let x=x1xnbe a vector over F2of length n.

A Boolean function fx1xnin n-variables is an arbitrary function from F2nto F2. It can also be interpreted as the output column of its truth table, i.e., a binary string of length 2n,

f=f000f100f111.E1

An n-variable function fis 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),

fx1xn=a0+1inaixi+1i<jnaijxixj++a12nx1x2xnE2

where the coefficients a0,aij,,a12nbelong to 01.

The algebraic degree, denoted by degf, is the number of variables in the highest order monomial with nonzero coefficient. A Boolean function with degf1is said to be affine, and the set of all n-variable affine functions is denoted by An. An affine function with the constant term equal to zero is called a linear function.

The nonlinearity of an n-variable function fis Nf=mingAndfg, which measures the minimum distance between fand all n-variable affine functions.

Many properties of Boolean function can be deduced from its Walsh spectra. The Walsh transform of fxin point ωF2nis an integer-valued function over F2ndefined by

Wfω=xF2n1fx+x·ω,E3

where x·ω=x1ω1++xnωnis the inner product of two vectors over F2n. The set {Wfω:ωF2n}is called the Walsh spectrum of f.

A Boolean function fxis called plateaued if its Walsh spectrum only takes three values, 0and ±2λ, where λis some positive integer.

Two Boolean functions fx,gxare said to be a pair of disjoint spectra functions if

Wfω·Wgω=0.E4

forallωF2n.

In terms of Walsh spectra, the nonlinearity of fis given by

Nf=2n112maxωF2nWfω.E5

A function is balanced if and only if Wf0=0, i.e., #xfx=0=#xfx=1.

An n-variable Boolean function fis said to be bent if its Walsh transform takes only two values ±2n2. Moreover, fis said to be semi-bent function if for all ωF2n

Wfω0±2n+12,ifnisodd0±2n+22,ifnis even.E6

The derivative of fxat aF2n, denoted by Dafx, is a Boolean function defined by Dafx=fx+a+fx, for all xF2n. The notion of the derivative of a Boolean function is extended to higher orders as follows.

Suppose a1akis a basis of a kdimensional subspace Vof F2n. The k-th derivative of fwith respect to V, denoted by DVfx, is a Boolean function defined by

DVfx=DakDak1Da1fx,E7

forallxF2n.

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 n1.

  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 2n1. On an even size Boolean space, there is a class of Boolean functions, called bent functions, that have maximum nonlinearity (2n12n21). 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 minputs 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 fis 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 dsuch that a given Boolean function for its complement 1+fadmits an annihilator (a nonzero Boolean function gsuch that 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 n2. 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 22n, an exhaustive search of functions which satisfy some of the properties above is practically impossible (unless the input variable space nis 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 nmdNffunction we specify an n-variable, m-resilient Boolean function f, algebraic degree d, and nonlinearity Nf. Siegenthaler [9] proved that m+dn+1if mn2. 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 nmdNffunction for any given nand mwhile at the same time attempting to optimize dand Nf. This optimization can be efficiently done for a small number of variables n5, but even some interesting open problems for n>5, related to the existence of 816116and 72456functions, 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 nmdNfoptimized function, such as the 72456function, one can generate a sequence of optimal plateaued 7+3i2+2i4+i27+3i122+2i+1functions, 1045480,13663968,168732256,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 nmnm12n12m+1and for m>n22) is given in [19]. The iteration once again employs a 72456function, whose 6-variable sub-functions have disjoint spectra, to construct a sequence of 7+4i2+3i4+i27+4i122+3i+1optimal plateaued functions (whose 7+4i1-variable sub-functions are again disjoint spectra functions). Nevertheless, this iterative method generates the functions with relatively large order of resiliency (1155964,158615872,19117258048,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 1155964function is generated whose 10-variable sub-functions are again disjoint spectra functions (two 1054452disjoint 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=8or n=9using the particular 72456function.

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 nare not extendable to bent functions in n+2variables. In [24] and recently in [25], a sufficient condition on two bent functions gand hused 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 aF2nsuch that Dafx=Dagx+1, then the function

hx=fx+gx+Dafx+DafxgxE8

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 i=1n/2x2i1x2i.

One may define a Boolean function f with neven to be a quadratic bent function of the form fx=i=1nbixi+1i<jnci,jxixjfor suitably chosen bi,ci,jF2. Furthermore, let gbe a Boolean function defined as gx=fx+i=1nαixi, where αiF2. Then, if aF2nis such that a·α=1, it can be shown that the function

hx=fx+gx+Dafx+Dafxgx

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 fbe bent Boolean function in even number of variables. For a,αF2nsuch that a·α=1define the function gas either

gx=fx+α·x+dfx+a+α·x+d,E9

where dF2. Then, the function

hx=fx+gx+Dafx+Dafxgx

is a semi-bent function.

Proof. Obviously, in both cases gis also a bent function, and if gx=fx+αx+d, we have

Dafx+Dagx=fx+fx+a+gx+gx+a
=fx+fx+a+fx+αx+d+fx+a+αx++d
=a·α=1.

A similar calculation gives that

Dafx+Dagx=1ifgx=fx+a+αx+d.

By Theorem 1 we deduce that hx=fx+gx+Dafx+Dafxgxis 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 g1, g2, apart from using affine equivalent functions g1and g2, satisfying Dag1x=Dag2x+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 fx1x2x3x4x5x6=x1x3x4+x2x3x4+x1x5x6+x2x5x6+x1x2+x3x5+x4x6+x5x6be a bent function of degree 3 over F26. Take a=001000and α=101000such that a·α=1. Define the function gas either

gx=fx+x1+x3fx+a+x1+x3=fx+x1+x3fx+x1x4+x2x4+x1+x3+x5,

where d=0F2.

Let us take gx=fx+x1+x3. We have

Dafx=fx+fx+a=fx+fx+x1x4+x2x4+x5=x1x4+x2x4+x5,

so that

fx+gx+Dafx=x1x4+x2x4+x1+x3+x5.

Then, using the idempotent property of Boolean ring,

fxgx=fxfx+x1+x3=fx1+x1+x3
=x1x3x4+x2x3x4+x1x5x6+x2x5x6+x1x2+x3x5+x4x6+x5x61+x1+x5
=x1x2x3x4+x1x2x5x6+x2x3x4x5+x1x2x5+x1x3x4+x1x3x5+x1x4x6
+x2x3x4+x4x5x6+x4x6.
fx+agx+a=fx+afx+a+x1+x3+1=fx+ax1+x3
=fx+x1x4+x2x4+x5x1+x3
=fxx1+x3+x1x4+x2x4+x5x1+x3.

After some simplification, we get

Dafxgx=fxgx+fx+agx+a
=fx+x1x4+x2x4+x5x1+x3
=x1x5x6+x2x5x6+x1x2+x1x4+x1x5+x2x4+x4x6+x5x6.

Finally,

hx=fx+gx+Dafx+Dafxgx
=x1x5x6+x2x5x6+x1x2+x1x5+x4x6+x5x6+x1+x3+x5.

It is easy to compute the Walsh spectrum of function hx, i.e., Whω=0±16, which means that hxis a semi-bent function.

Notice that the standard derivation rule for multiplication does not apply for our definition of derivatives. Indeed, the derivative Dafxgx=fxgx+fx+agx+ais different from gxDafx+fxDagx=fx+agx+fxgx+a.Furthermore, using the fact that DaDafx=0for any Boolean function f, we have

Dahx=hx+hx+a
=fx+gx+Dafx+Dafxgx+fx+a+gx+a+Dafx+a+Dafx+agx+a
=Dafx+Dagx+DaDafx+DaDafxgx
=Dafx+Dagx=1.

Thus, the element ais always a linear structure of hx. Nevertheless, we show that under certain sufficient conditions, ais the only linear structure of hx. We have the following theorem.

Theorem 3. Let hbe defined as in Theorem 2, and assume that a bent function fxis such that degDbfx>1, for any bF2n0.Then hhas a single linear structure, that is, Dbhx=hx+hx+bis a constant function only for b=a.

Proof. Assume that gx=fx+a+αx+d. Without loss of generality, we can take d=0.Then,

Dbfx+Dbgx=fx+fx+b+gx+gx+b
=fx+fx+b+fx+a+αx+a+d+fx+a+b+αx+a+b+d
=DbDafx+αb,

where DbDafx=fx+fx+a+fx+b+fx+a+b, and therefore

Dbhx=DbDafx+αb+DbDafx+DbDafxgx=DbDafxgx+αb.

Hence, Dbhxis constant if and only if DbDafxgxis constant. But,

DbDafxgx=Dbfxgx+fx+agx+a
=Dbfxfx+a+αx+fx+afx+αx+a
=Dbαxfx+fx+a+αafx+a
=Dbαxfx+fx+a+fx+a
=αxDbDafx+αbfx+b+fx+a+b+fx+a+fx+a+b.

Thus, if αb=0, then Dbhxis constant if and only if

αxDbDafx=fx+a+fx+a+b
αxfx+fx+a+fx+b+fx+a+b=fx+a+fx+a+b
αx+1fx+a+fx+a+b+αxfx+fx+b=0
αx+1Dbfx+a+αxDbfx=0
αxDbfx+a+αxDbfx+Dbfx+a=0.

There are four possible cases:

  1. αxDbfx+a=αxDbfx=Dbfx+a=0, i.e., Dbfx+a=0fx+a=fx+a+bb=0.A contradiction.

  2. αxDbfx+a=αxDbfx=1Dbfx+a=0, i.e., Dbfx+a=0b=0.A contradiction.

  3. αxDbfx+a=0αxDbfx=Dbfx+a=1, i.e., Dbfx+a=0b=0.A contradiction.

  4. αxDbfx+a=Dbfx+a=1αxDbfx=0, i.e., Dbfx+a=0b=0.A contradiction.

On the other hand, if αb=1, then Dbhxis constant if and only if

αxDbDafx=fx+a+fx+b
αxfx+fx+a+fx+b+fx+a+b=fx+a+fx+b
αx+1fx+a+fx+b+αxfx+fx+a+b=0.

It is obvious that fx+a=fx+bis equivalent to fx=fx+a+b. Thus, the above equation is constant if and only if fx+a=fx+b, which implies that a=b. The sufficiency of this condition is obvious. For the necessity, we first observe that for abthe functions fx+a+fx+band fx+fx+a+bbeing derivatives of a bent function fare both nonconstant. Then, assuming that

DbDafx=fx+fx+a+fx+b+fx+a+b=0,

it would imply that fx+a+fx+bis constant, a contradiction. On the other hand, the function αxDbDafxcannot be balanced, unless DbDafx=αx. Because of the assumption, degfx+a+fx+b>1and therefore cannot be equal to αx.

The proof for the case gx=fx+αx+dis similar as above, and it is omitted here. q.e.d.

Notice the condition in Theorem 3 that degDbfx>1is sufficient but may not be necessary. An analysis of other cryptographic criteria appears to be difficult due to the dependency of hon the choice of a bent function fand the use of the derivative Dafxgxin its definition, which is illustrated in the following example.

Example 2. Let nbe even and fxy=x·y, where x,yF2kis a bent function and belongs to the Maiorana-McFarland class. Then, defining gxy=fx+ay+b+αβ·xyfor a nonzero abF2k×F2ksuch that αβ·ab=1, we have

gxy=x·y+α+b·x+a+β·y+a·b,

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

Dabfxy=x·b+a·y+a·b, so that

fxy+gxy+Dabfxy=α·x+β·y.

Then, using the idempotent property of Boolean ring,

fxy·gxy=x·yx·y+α+b·x+a+β·y+a·b
=1+a·bxy+α+b·x+a+β·yx·y.

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

Dabfxygxy=x·y+b·x+a·y+a·b(1+a·b+α·x+α·a+b·x
+a·b+a·y+β·y+β·b)
=x·y+b·x+a·y+a·bα·x+b·x+a·y+β·y+a·b+β·b
=x·y+b·x+a·y+a·bα+b·x+β+a·y+a·b+β·b.

Finally,

hxy=fxy+gxy+Dabfxy+Dabfxygxy
=x·y+α·x+β·yb·x+a·y+a·b+1+b·x+a·y+a·b1+β·b.

More precisely, it can be illustrated using Example 1.

Example 3. Let fx1x2x3x4x5x6=x1x3x4+x2x3x4+x1x5x6+x2x5x6+x1x2+x3x5+x4x6+x5x6be a bent function of degree 3 over F26. Take a=001000and α=101000such that a·α=1. Define the function gas gx=fx+x1+x3.By Example 1 we have

hx=x1x5x6+x2x5x6+x1x2+x1x5+x4x6+x5x6+x1+x3+x5.

Moreover, by Theorem 2 hhas a single linear structure only for b=a. Indeed,

Dahx=hx+hx+a
=x1x5x6+x2x5x6+x1x2+x1x5+x4x6+x5x6+x1+x3+x5+
+x1x5x6+x2x5x6+x1x2+x1x5+x4x6+x5x6+x1+x3+1+x5
=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).

© 2019 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Samed Bajrić (May 10th 2019). Implementing Symmetric Cryptography Using Sequence of Semi-Bent Functions, Modern Cryptography - Current Challenges and Solutions, Menachem Domb, IntechOpen, DOI: 10.5772/intechopen.85023. Available from:

chapter statistics

115total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Survey of RSA Vulnerabilities

By Anthony Overmars

Related Book

First chapter

Introductory Chapter: Chromatic Dispersion Monitoring in Synchronization Channel of Quantum Key Distribution Systems with Carrier Modulation Coding

By Oleg G. Morozov

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us