# 1-Resilient Boolean Functions on Even Variables with Almost Perfect Algebraic Immunity

Authors: Gang Han; Yu Yu; Xiangxue Li; Qifeng Zhou; Dong Zheng; Hui Li
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Several factors (e.g., balancedness, good correlation immunity) are considered as important properties of Boolean functions for using in cryptographic primitives. A Boolean function is perfect algebraic immune if it is with perfect immunity against algebraic and fast algebraic attacks. There is an increasing interest in construction of Boolean function that is perfect algebraic immune combined with other characteristics, like resiliency. A resilient function is a balanced correlation-immune function. This paper uses bivariate representation of Boolean function and theory of finite field to construct a generalized and new class of Boolean functions on even variables by extending the Carlet-Feng functions. We show that the functions generated by this construction support cryptographic properties of 1-resiliency and (sub)optimal algebraic immunity and further propose the sufficient condition of achieving optimal algebraic immunity. Compared experimentally with Carlet-Feng functions and the functions constructed by the method of first-order concatenation existing in the literature on even (from 6 to 16) variables, these functions have better immunity against fast algebraic attacks. Implementation results also show that they are almost perfect algebraic immune functions.


---

## Body

## 1. Introduction

Boolean functions are one of the most important cryptographic primitives for stream ciphers, block ciphers, and hash functions in cryptography [1–4]. For instance, we take Boolean functions extensively as filter and combination generators of stream ciphers based on linear feedback shift registers [3]. Cryptographic criteria for Boolean functions include balancedness, algebraic degree, nonlinearity, and correlation immunity. An overview of cryptographic criteria for Boolean functions with extensive bibliography is given in [1].The study of the cryptographic criteria of Boolean functions is essential because of the connections between known cryptanalytic attacks and these criteria [4]. An improperly chosen Boolean function will render the system open to various kinds of attacks. Take the property of balancedness (i.e., its Hamming weight = 2n-1), for example, the classical cryptographic criterion for designing Boolean function is useful in preventing the system from leaking statistical information on the plaintext when the ciphertext is known.


### 1.1. Related Work

#### 1.1.1. Resilient Functions

Resilient functions (see Definition3), first studied by Siegenthaler in [5], are a special class of Boolean functions and find many interesting applications in stream ciphers.A functionf is said to be correlation-immune of the order t if the output of the function is statistically independent of the combination of any t of its inputs [6]. In 1988, Xiao and Massey introduced (by using properties of Walsh spectra) the notion of correlation immunity as an important cryptographic measure of a Boolean function with respect to its resistance against the correlation attack (which can be seen as solving a system of multivariate linear equations) [7].In [8], Maitra and Sakar discussed the various methods for constructing resilient functions, and their results constitute a subset of a larger set of resilient functions.


#### 1.1.2. Algebraic Attacks

In recent years, algebraic attack [9–11] has received a lot of attention in cryptography. This kind of attacks dates back to 2003 when Courtois and Meier [10] proposed algebraic attack on stream ciphers with linear feedback, which is much powerful (breaking stream ciphers satisfying the previously known design criteria in at most the square root of the complexity of the previously known generic attack). Thus the new cryptographic property of Boolean functions-algebraic immunity (AI), the minimum algebraic degree of annihilators of f or f+1, was introduced by Meier et al. [11] to measure the ability of Boolean functions to resist algebraic attacks.It was shown by Courtois and Meier [10] that maximum AI ofn-variable Boolean functions is n/2. The properties and constructions of Boolean functions with maximum AI are concerned in a large number of works (to name a few [9, 12–16]). The problem of efficiently constructing balanced Boolean functions with optimal algebraic immunity (and/or other cryptographic properties) is thus of great significance.


#### 1.1.3. Fast Algebraic Attacks

Although Boolean functions with high (or optimal, ideally) algebraic immunity can effectively resist algebraic attack, it does not rule out the possibility that these functions are vulnerable to the improved algebraic attack, that is, fast algebraic attack [17, 18].Therefore, the cryptographic community turns to address much concern on Boolean functions resisting fast algebraic attack, besides their algebraic immunity. At Asiacrypt 2012, Liu et al. [20] initiated perfect algebraic immune (PAI) functions, Boolean functions with perfect immunity against algebraic and fast algebraic attacks. Although we know that the Carlet-Feng functions [9] on 2s+1 variables and the modified Carlet-Feng functions on 2s variables are shown to be perfect algebraic immune functions [20], it is still not easy in general to explore perfect algebraic immune functions, and we do not see much successful attempt made in the literature on perfect algebraic immune functions on even variables. Thus, it is significant in both theory and practice to construct (almost) perfect algebraic immune functions on even variables with other cryptographic properties (such as resiliency) simultaneously.We notice that Pan et al. [19] presented a construction for a class of 1-resilient Boolean functions with optimal algebraic immunity on an even number of variables by dividing them into two correlation classes, that is, equivalence classes. However, the cryptographic properties of the resulting functions are highly related to those of the initial functions we choose, and in particular, one would not expect strong resistance against fast algebraic attack in the resulting Boolean functions.


### 1.2. Our Contributions

In the paper, we use primitive polynomials to construct a class of Boolean functions on even variables, achieving at the same time several desirable features. For the resulting functions, we prove the properties of 1-resiliency (see Definition3) and suboptimal algebraic immunity (see Definition 4). We also propose the sufficient condition of achieving optimal algebraic immunity.Compared with Carlet-Feng functions [9] and the functions constructed by the method of first-order concatenation existing in the literature on even (from 6 to 16) variables [19], ours show better immunity against fast algebraic attacks. We check that our constructions are almost perfect algebraic immune functions (see Definition 5).


### 1.3. Roadmap

The remainder of the paper is organized as follows. Section2 reviews some definitions related to Boolean functions and their cryptographic criteria. Section 3 presents our proposed construction of almost perfect algebraic immune resilient functions on even variables, followed by resiliency analysis in Section 4, by algebraic immunity analysis in Section 5, and by fast algebraic immunity analysis in Section 6, sequentially. Concluding remarks are located in Section 7.


### 1.4. Notations

We summarize in Notations the notations used in this paper.


## 1.1. Related Work

### 1.1.1. Resilient Functions

Resilient functions (see Definition3), first studied by Siegenthaler in [5], are a special class of Boolean functions and find many interesting applications in stream ciphers.A functionf is said to be correlation-immune of the order t if the output of the function is statistically independent of the combination of any t of its inputs [6]. In 1988, Xiao and Massey introduced (by using properties of Walsh spectra) the notion of correlation immunity as an important cryptographic measure of a Boolean function with respect to its resistance against the correlation attack (which can be seen as solving a system of multivariate linear equations) [7].In [8], Maitra and Sakar discussed the various methods for constructing resilient functions, and their results constitute a subset of a larger set of resilient functions.


### 1.1.2. Algebraic Attacks

In recent years, algebraic attack [9–11] has received a lot of attention in cryptography. This kind of attacks dates back to 2003 when Courtois and Meier [10] proposed algebraic attack on stream ciphers with linear feedback, which is much powerful (breaking stream ciphers satisfying the previously known design criteria in at most the square root of the complexity of the previously known generic attack). Thus the new cryptographic property of Boolean functions-algebraic immunity (AI), the minimum algebraic degree of annihilators of f or f+1, was introduced by Meier et al. [11] to measure the ability of Boolean functions to resist algebraic attacks.It was shown by Courtois and Meier [10] that maximum AI ofn-variable Boolean functions is n/2. The properties and constructions of Boolean functions with maximum AI are concerned in a large number of works (to name a few [9, 12–16]). The problem of efficiently constructing balanced Boolean functions with optimal algebraic immunity (and/or other cryptographic properties) is thus of great significance.


### 1.1.3. Fast Algebraic Attacks

Although Boolean functions with high (or optimal, ideally) algebraic immunity can effectively resist algebraic attack, it does not rule out the possibility that these functions are vulnerable to the improved algebraic attack, that is, fast algebraic attack [17, 18].Therefore, the cryptographic community turns to address much concern on Boolean functions resisting fast algebraic attack, besides their algebraic immunity. At Asiacrypt 2012, Liu et al. [20] initiated perfect algebraic immune (PAI) functions, Boolean functions with perfect immunity against algebraic and fast algebraic attacks. Although we know that the Carlet-Feng functions [9] on 2s+1 variables and the modified Carlet-Feng functions on 2s variables are shown to be perfect algebraic immune functions [20], it is still not easy in general to explore perfect algebraic immune functions, and we do not see much successful attempt made in the literature on perfect algebraic immune functions on even variables. Thus, it is significant in both theory and practice to construct (almost) perfect algebraic immune functions on even variables with other cryptographic properties (such as resiliency) simultaneously.We notice that Pan et al. [19] presented a construction for a class of 1-resilient Boolean functions with optimal algebraic immunity on an even number of variables by dividing them into two correlation classes, that is, equivalence classes. However, the cryptographic properties of the resulting functions are highly related to those of the initial functions we choose, and in particular, one would not expect strong resistance against fast algebraic attack in the resulting Boolean functions.


## 1.1.1. Resilient Functions

Resilient functions (see Definition3), first studied by Siegenthaler in [5], are a special class of Boolean functions and find many interesting applications in stream ciphers.A functionf is said to be correlation-immune of the order t if the output of the function is statistically independent of the combination of any t of its inputs [6]. In 1988, Xiao and Massey introduced (by using properties of Walsh spectra) the notion of correlation immunity as an important cryptographic measure of a Boolean function with respect to its resistance against the correlation attack (which can be seen as solving a system of multivariate linear equations) [7].In [8], Maitra and Sakar discussed the various methods for constructing resilient functions, and their results constitute a subset of a larger set of resilient functions.


## 1.1.2. Algebraic Attacks

In recent years, algebraic attack [9–11] has received a lot of attention in cryptography. This kind of attacks dates back to 2003 when Courtois and Meier [10] proposed algebraic attack on stream ciphers with linear feedback, which is much powerful (breaking stream ciphers satisfying the previously known design criteria in at most the square root of the complexity of the previously known generic attack). Thus the new cryptographic property of Boolean functions-algebraic immunity (AI), the minimum algebraic degree of annihilators of f or f+1, was introduced by Meier et al. [11] to measure the ability of Boolean functions to resist algebraic attacks.It was shown by Courtois and Meier [10] that maximum AI ofn-variable Boolean functions is n/2. The properties and constructions of Boolean functions with maximum AI are concerned in a large number of works (to name a few [9, 12–16]). The problem of efficiently constructing balanced Boolean functions with optimal algebraic immunity (and/or other cryptographic properties) is thus of great significance.


## 1.1.3. Fast Algebraic Attacks

Although Boolean functions with high (or optimal, ideally) algebraic immunity can effectively resist algebraic attack, it does not rule out the possibility that these functions are vulnerable to the improved algebraic attack, that is, fast algebraic attack [17, 18].Therefore, the cryptographic community turns to address much concern on Boolean functions resisting fast algebraic attack, besides their algebraic immunity. At Asiacrypt 2012, Liu et al. [20] initiated perfect algebraic immune (PAI) functions, Boolean functions with perfect immunity against algebraic and fast algebraic attacks. Although we know that the Carlet-Feng functions [9] on 2s+1 variables and the modified Carlet-Feng functions on 2s variables are shown to be perfect algebraic immune functions [20], it is still not easy in general to explore perfect algebraic immune functions, and we do not see much successful attempt made in the literature on perfect algebraic immune functions on even variables. Thus, it is significant in both theory and practice to construct (almost) perfect algebraic immune functions on even variables with other cryptographic properties (such as resiliency) simultaneously.We notice that Pan et al. [19] presented a construction for a class of 1-resilient Boolean functions with optimal algebraic immunity on an even number of variables by dividing them into two correlation classes, that is, equivalence classes. However, the cryptographic properties of the resulting functions are highly related to those of the initial functions we choose, and in particular, one would not expect strong resistance against fast algebraic attack in the resulting Boolean functions.


## 1.2. Our Contributions

In the paper, we use primitive polynomials to construct a class of Boolean functions on even variables, achieving at the same time several desirable features. For the resulting functions, we prove the properties of 1-resiliency (see Definition3) and suboptimal algebraic immunity (see Definition 4). We also propose the sufficient condition of achieving optimal algebraic immunity.Compared with Carlet-Feng functions [9] and the functions constructed by the method of first-order concatenation existing in the literature on even (from 6 to 16) variables [19], ours show better immunity against fast algebraic attacks. We check that our constructions are almost perfect algebraic immune functions (see Definition 5).


## 1.3. Roadmap

The remainder of the paper is organized as follows. Section2 reviews some definitions related to Boolean functions and their cryptographic criteria. Section 3 presents our proposed construction of almost perfect algebraic immune resilient functions on even variables, followed by resiliency analysis in Section 4, by algebraic immunity analysis in Section 5, and by fast algebraic immunity analysis in Section 6, sequentially. Concluding remarks are located in Section 7.


## 1.4. Notations

We summarize in Notations the notations used in this paper.


## 2. Preliminaries

LetF2n be the vector space of dimension n over the finite field F2. A Boolean function f on n variables is a mapping from F2n to F2. By the truth table of a Boolean function on n input variables x=(x1,…,xn), we mean the 2n length binary string {f0,0,…,0,f0,0,…,1,f0,…,1,0,…, f1,…,1,1}. The set ofn-variable Boolean functions on F2n is denoted by Bn.The Hamming weight off is the number of 1s in the binary string, denoted by wt(f). The support of f is the set x∈F2n∣fx=1 and is denoted by supp(f); that is, wt(f)=suppf. The Hamming distance dH(f,g) between two Boolean functions f and g is the Hamming weight of their difference f+g (i.e., dH(f,g)=wt(f+g)), where + is the addition on F2.Definition 1 (balancedness).
A Boolean functionf is balanced if its output is equally distributed, that is, the number of 0 elements in its truth table is equal to the number of 1 elements. In other words, an n-variable Boolean function f is balanced if and only if wt(f)=2n-1.Forf(x)∈Bn, it can be uniquely represented as a multivariate polynomial in the ring(1)F2x1,x2,…,xnx12-x1,…,xn2-xn,and its algebraic normal form (ANF) is written as follows:(2)fx1,…,xn=∑I⊆1,2,…,naI∏i∈Ixi,aI∈F2.Elements of a finite field can be represented in a variety of ways, depending on the choice of basis for the representation. Let(α1,α2,…,αn) be a basis of F2n over F2. Then, we can build an isomorphism between F2n and F2n:(3)x1,x2,…,xn⟼x1·α1+x2·α2+⋯+xn·αnand we can further represent f:F2n→F2 as the polynomial (4)fx=∑i=02n-1aixi,ai∈F2n.Now supposen=2k. Similarly, f:F2k×F2k→F2 can be represented uniquely as bivariate polynomial(5)fx,y=∑i=02k-1∑j=02k-1ai,jxiyj,ai,j∈F2kand the algebraic degree off is (6)deg⁡f=maxai,j≠0⁡wti+wtj,0≤i,j≤2k-1,where wt(i) is the Hamming weight of the binary string corresponding to the integer i; namely, (7)wti=i1+i2+⋯+iτif i=∑l=1τil2l.Definition 2 (Walsh spectrum).
Letf:F2k×F2k→F2, f(x,y)=∑i=02k-1∑j=02k-1ai,jxiyj, ai,j∈F2k, and (a,b)∈F2k×F2k. The Walsh spectrum of f (at (a,b)) is defined as (8)Wfa,b=∑x,y∈F2k×F2k-1fx,y+Tr1nax+by,where Tr1n:F2n→F2 is the trace function, defined as (9)Tr1nα=α+α2+α22+⋯+α2n-1,∀α∈F2n.Correlation immunity has long been recognized as one of the critical indicators of nonlinear combining functions of shift registers in stream generators [21, 22]. A high correlation immunity is generally a very desirable property, in view of various successful correlation attacks against a number of stream ciphers (see, e.g., [23]). The concept of correlation-immune functions was introduced by Siegenthaler [5]. Xiao and Massey gave an equivalent definition [7, 24].Definition 3 (correlation immunity).
A functionf is called an mth-order correlation-immune function if(10)Wfω=0,∀ω∈F2n,1≤wtω≤m,where wt(ω) is the Hamming weight of ω, that is, the number of nonzero components.
Iff is also balanced, then it is calledm-resilient.Definition 4 (annihilator and algebraic immunity).
Givenf∈Bn, we define(11)ANf=g∈Bn∣f·g=0,where · is the multiplication on F2. Any g∈AN(f) is called an annihilator off.The algebraic immunity off, denoted by AI(f), is defined as the minimum degree of nonzero annihilators off or f+1; that is,(12)AIf=min⁡deg⁡g∣0≠g∈ANf∪ANf+1.It is known [10] that AI(f)≤n/2, for any f∈Bn. If AI(f)=n/2, then we say then-variable Boolean function f has optimal algebraic immunity.At Crypto 2003, Courtois [17] proposed fast algebraic attacks (FAAs). The key idea is to decrease the degree of the equations (a multivariate polynomial system of equations over a finite field) using a precomputation algorithm. More formally, if there existsn-variable Boolean function g of low degree such that deg⁡(f·g) is somewhat not large, then one can perform fast algebraic attack on f with much confidence. To measure the resistance against fast algebraic attack, Liu et al. introduced fast algebraic immunity (FAI), which is considered as an important cryptographic property for Boolean functions used in stream ciphers:(13)FAIf=min⁡2AIf,deg⁡g+deg⁡f·g,where 1≤deg(g)<AI(f).It is folklore thatFAI(f)≤n [10, 25].Almost all the symmetric Boolean functions including the functions with good algebraic immunity behave badly against FAAs [18, 25]. However, Carlet-Feng function, a class ofn-variable balanced Boolean functions with the maximum algebraic immunity as well as good nonlinearity [9], was proved to have almost optimal resistance and even optimal resistance against FAAs if n=2s+1 exactly with positive integer s [20]. Another class of even n-variable balanced Boolean functions with the maximum algebraic immunity and large nonlinearity, called Tang-Carlet function [26], was also proved to have almost optimal resistance [27]. Moreover, the immunity of some rotation symmetric Boolean functions against FAAs was also analyzed [18, 28].The following definition provides the functionalities of both algebraic immunity and fast algebraic immunity.Definition 5 ((almost) perfect algebraic immunity).
Letf be ann-variable Boolean function. The functionf is said to be perfect algebraic immune (PAI) if, for any positive integers e<n/2, the product f·g has degree at least n-e for any nonzero function g(g∈Bn) of degree at most e.
The functionf is said to be almost perfect algebraic immune if, for any positive integers e<n/2, the product f·g has degree at least n-e-1 for any nonzero function g (g∈Bn) of degree at moste.


## 3. The Proposed Construction

Resilient functions (see Definition3) are a special class of Boolean functions and find many interesting applications in stream ciphers. In [8], Maitra and Sakar discussed the various methods of creation of resilient functions, and functions constructed by these methods constitute a subset of a larger set of all resilient functions.Pan et al. [19] presented a construction for a class of 1-resilient Boolean functions with optimal algebraic immunity on an even number of variables by dividing them into two correlation classes. More precisely, Pan et al. proposed a secondary construction (i.e., Siegenthaler’s [6] construction) by concatenating two balanced Boolean functions f, g with odd variables n, where deg⁡(f)=n-1, AI(f)=(n+1)/2. They can prove the existence of a nontrivial pair (f,g) applied in the construction. But they can only construct a part of 1-resilient Boolean functions with optimal algebraic immunity by using these pairs. Pan et al. generalized the construction to a larger class of functions with suboptimal algebraic immunity on any number (>2) of variables. However, the cryptographic properties of the resulting functions are highly related to those of the initial functions they chose as building block, and in particular, this does not rule out the possibility that these functions are vulnerable to fast algebraic attack; that is, one would not expect strong resistance against fast algebraic attack in the resulting Boolean functions. More details on the rationale of their constructions can be found in [19] where two constructions are presented and security properties are analyzed mathematically step by step. In Section 6, we also compare the properties of fast algebraic immunity between our construction and the proposal of Pan et al. [19].This section will present our construction followed by cryptographic property analysis in the next sections.Throughout the rest of the paper, letk, s, u, v, m be positive integers, n=2k, k≥3, 0≤s≤2k-2, and 2k-1-1≤m≤2k-2. Let α be a primitive element of finite field F2k, and β=α(u+v)-1∈F2k.Set(14)Z2k-1≜0,1,…,2k-1,Δm,s≜s,s+1,…,2k-1+s-2∪m+s,P≜u,v∣gcdu+vu,2k-1=1,0<u,v<2k-1.For any(u,v)∈P, definen-variable Boolean function f whose support supp(f) consists of the following four sets:(15)⋃i=s2k-1+s-2x,y∣x=αiy-1,y∈F2k∗,βui,βvi∣i∈Z2k-1∖Δm,s,βui,0∣i∈Δm,s,0,βvi∣i∈Δm,s.In the coming sections, we will discuss its cryptographic properties: resiliency, algebraic immunity, and fast algebraic immunity. In particular, we will show that the functions derived from our construction are 1-resilient and with almost perfect algebraic immunity.


## 4. Resiliency of the Proposed Construction

Nonlinear Boolean functions are generally used in symmetry cryptography. It is not surprising that the functions should have sufficiently simple scheme implementation in hardware. Besides, they must satisfy certain criteria to resist different attacks (e.g., correlation attacks suggested by Siegenthaler [29] and different types of linear attacks). One of the important factors is good correlation immunity (of orderm); namely, the output should be statistically independent of combination of anym its inputs. And 1-resiliency specifies a balanced correlation-immune of order 1 Boolean function.Theorem 6.
Suppose thatf is a Boolean function derived from our construction. Then we have that f is 1-resilient.Proof.
According to the definition of resiliency (see Definition3), we first show that the function derived from our construction is balanced.
In fact, we have that(16)wtf=2k-1-12k-1+Z2k-1∖Δm,s+2Δm,s=22k-1;thus, the functionf is balanced as expected.
SetΩ=F2k×F2k. We know that (17)∑x,y∈Ω-1Tr1kax+by=0;then, for any (a,b)∈Ω∖{(0,0)}, it holds that(18)Wfa,b=∑x,y∈Ω-1fx,y+Tr1kax+by=∑x,y∈Ω∖suppf-1Tr1kax+by-∑x,y∈suppf-1Tr1kax+by=-2∑x,y∈suppf-1Tr1kax+by.Plugging the four sets of supp(f) into ∑(x,y)∈supp(f)(-1)Tr1k(ax+by), we have that(19)∑x,y∈suppf-1Tr1kax+by=∑i=s2k-1+s-2∑y∈F2k∗-1Tr1kaαiy-1+by+∑i∈Δm,s-1Tr1kaβui+∑i∈Z2k-1∖Δm,s-1Tr1kaβui+bβvi+∑i∈Δm,s-1Tr1kbβvi.Now we consider the following two cases.
Case  1 (a≠0andb=0). We have (20)∑x,y∈suppf-1Tr1kax+by=2k-1-1-1+Δm,s+∑i∈Z2k-1∖Δm,s-1Tr1kaβui+∑i∈Δm,s-1Tr1kaβui=0.
Case  2 (a=0andb≠0). We have (21)∑x,y∈suppf-1Tr1kax+by=2k-1-1-1+Δm,s+∑i∈Z2k-1∖Δm,s-1Tr1kbβvi+∑i∈Δm,s-1Tr1kbβvi=0.
Therefore, we can conclude thatWf(a,b)=0, for any (a,b)∈Ω∖{(0,0)} and ab=0. According to Definition 3, we know thatf is 1-resilient.


## 5. Algebraic Immunity of the Proposed Construction

Algebraic attacks have become a powerful tool that can be used for almost all types of cryptographic systems. Algebraic immunity defined for a Boolean function measures the resistance of the function against algebraic attacks. The properties and constructions of Boolean functions with high algebraic immunity are concerned in extensive work, for example, [9, 12–16].In this section, we will analyze the algebraic immunity of the proposed construction. First we have the following lemma.Lemma 7 (see [30, 31]).
Suppose the integerk≥3; it holds that
(1) for any0≤t≤2k-2 we have (22)#i,j∣0≤i,j≤2k-2,i-j≡tmod⁡2k-1,wti+wtj≤k-1≤2k-1;
(2) for any1≤t≤2k-2 we have(23)#i,j∣0≤i,j≤2k-2,i-j≡tmod⁡2k-1,wti+wtj≤k-1≤2k-1-1.Theorem 8.
Let the Boolean functionf be derived from the proposed construction. We have
(1)AI(f)≥k-1;
(2)AI(f)=k (i.e., f has optimal algebraic immunity) if m+s=2k-1-1  or  0(mod2k-1).Proof.
Leth be an annihilator of f such that f·h=0, degh<k. Suppose that (24)hx,y=∑i=02k-2∑j=02k-2hi,jxiyj.For any (x,y)∈supp(f), we have h(x,y)=0 and (25)⋃i=s2k-1+s-2x,y∣x=αiy-1,y∈F2k∗⊂suppf.
Then, for anys≤l≤2k-1+s-2, 0≤s≤2k-2, and y∈F2k∗, it holds that(26)0=hαly-1,y=∑i=02k-2∑j=02k-2hi,jαliyj-i=∑t=02k-2htαyt,where(27)htα=∑0≤i,j≤2k-2,i-j≡tmod2k-1hi,jαli,0≤t≤2k-2.
Suppose thaty travels in F2k∗. Then the coefficients yt in (26) will make up a coefficient matrix which is Vandermonde-like. From the invertibility property of Vandermonde matrix, we know that (28)∑0≤i,j≤2k-2,i-j≡tmod2k-1hi,jαli=0for any 0≤t≤2k-2 and s≤l≤2k+s-2.
Now we consider the following two cases.
Case  1 (1≤t≤2k-2). From Lemma 7, we know that the number of different hi,j in (28) is no more than 2k-1-1. Thus we can further assume these hi,j are {hi1,j1,hi2,j2,…,hi2k-1-1,j2k-1-1}.
Set(29)H≜hi1,j1,hi2,j2,…,hi2k-1-1,j2k-1-1T,M≜αi1sαi2s⋯αi2k-1-1sαi1s+1αi2s+1⋯αi2k-1-1s+1⋮⋮⋱⋮αi12k-1+s-2αi22k-1+s-2⋯αi2k-1-12k-1+s-2;then, we have (30)M·H=0.
Now, the invertibility property of Vandermonde matrix tells that(31)H=0.
Namely, for any0≤i,j≤2k-2, and 1≤t≤2k-2, we have(32)hi,j=0ifi-j≡tmod⁡2k-1.
Therefore, for any1≤j≤2k-2, it holds that (33)h0,j=0.As (0,1)∈supp(f), we have (34)h0,1=0=∑j=02k-2h0,j;thus h0,0=0 follows.
Case  2 (t=0, i.e.,i=j). From Lemma 7, we know that the number of different hi,j in (28) is no more than 2k-1-1. Thus, for any 1≤i≤2k-2, we have (35)hi,i=0.
Putting all together, we know that(36)h≡0;namely, there is not any annihilator of degree lower thank.
Next we considerf+1. Its support supp(f+1) consists of the following sets:(i)
⋃i=2k-1+s-12k-1+s-2x,y∣x=αiy-1,y∈F2k∗∖βvi(ii)
βui,0∣i∈Z2k-1∖Δm,s(iii)
0,βvi∣i∈Z2k-1∖Δm,s(iv)
{(0,0),(βu(m+s),βv(m+s))}.Assume thath is an annihilator off+1, deg(h)<k.
Without loss of generality, set(37)hx,y=∑i=02k-2∑j=02k-2hi,jxiyj.Denote(38)h1≜∑i=02k-3∑j=02k-3hi,jxiyjh2≜∑i=02k-2hi,2k-2xiy2k-2h3≜∑j=02k-2h2k-2,jx2k-2yj;then (39)hx,y=h1+h2+h3.
For any(x,y)∈supp(f+1), we have(40)hx,y=0,⋃i=2k-1+s-12k+s-2x,y∣x=αiy-1,y∈F2k∗∖βvi⊂suppf+1.
Then, for any2k-1+s-1≤l≤2k+s-2 and y∈F2k∗∖{βv}, it holds that(41)0=h1αly-1,y=∑t=02k-3htαyt,where(42)htα=∑0≤i,j≤2k-3,i-j≡tmod2k-1hi,jαli,0≤t≤2k-3.
Suppose thaty travels in F2k∗∖{βv}. Then the coefficients yt in (41) will make up a coefficient matrix which is Vandermonde-like. Similarly, Lemma 7 will lead to the fact that (43)h1=0,and AI(f)≥k-1 follows.
Ifm+s=2k-1-1 or 0(mod2k-1), then (note that deg⁡(h(2))<k)(44)h2=h0,2k-2y2k-2.
On the other hand, we have(45)0,βvi∣i∈Z2k-1∖Δm,s⊂suppf+1.
Thus for anyi∈Z2k-1∖Δm,s,(46)h20,βvi=0;therefore(47)h0,2k-2=0.
Similarly, we have(48)h2k-2,0=0.
In a nutshell, one can conclude thatAI(f)=k (i.e.,f has optimal algebraic immunity) if m+s=2k-1-1 or 0(mod2k-1). And this completes the proof.


## 6. Fast Algebraic Immunity of the Proposed Construction

Algebraic attacks are based on the establishment and processing of an overdefined system of nonlinear equations involving the secret key and the keystream sequence. The system can be practically solved, and thus the secret key is compromised, only if the equations are of low degree. Courtois and Meier demonstrated that a successful algebraic attack exists when the Boolean functionf (or its complement f+1) has a low degree annihilator (a nonzero Boolean function g, such that fg=0). At crypto 2003, Courtois [17] further generalized the standard algebraic attack to an improved version, fast algebraic attack (see also [32]), by presenting a method that allows substantially reducing the complexity of the attack. Several stream ciphers appeared to be vulnerable to the FAA, such as Toyocrypt, LILI-128, and the keystream generator that is used in E0 cipher. Fast algebraic attacks are considered to be more difficult to study than the standard algebraic attack, and thus a design with good immunity against FAA is expected.Definition 9 (Carlet-Feng function [9]).
Letf be an n-variable Boolean function, α be a primitive element in F2n, and s be an integer, 0≤s≤2n-2. Denote(49)Δs≜αs,αs+1,…,αs+2n-1-2.We call f a Carlet-Feng function if supp(f)=Δs.Theorem 10 (see [9]).
Carlet-Feng functionf derived from Definition 9 has a good behavior against fast algebraic attacks.In particular, Carlet and Feng checked that no nonzero functiong of degree at most e and no function h of degree at most d exist such that f·g=h, when (e,d)=(1,n-2) for n odd and (e,d)=(1,n-3) for n even.This has been checked forn≤12 and also conjectured for every n; for e>1, pairs (g,h) of degrees (e,d) such that e+d<n-1 were never observed; precisely, the nonexistence of such pairs could be checked exhaustively for n≤9 and e<n/2, for n=10 and e≤3, and for n=11 and e≤2.This suggests that this class of functions, even if not always optimal against fast algebraic attacks, has a very good behavior.Pan et al. presented [19] a construction for a class of 1-resilient Boolean functions with optimal algebraic immunity on an even number of variables by dividing them into two correlation classes, that is, equivalence classes. The coming result states the construction.Theorem 11 (see [19]).
Letn be any odd integer (n≥3), f be a balanced Boolean function with maximum degree n-1 and optimal algebraic immunity (n+1)/2, and g be an annihilator of f. Then the following is 1-resilient Boolean function with optimal algebraic immunity:(50)h=f∥g=1+xn+1f+xn+1g∈F2n+1.
Letf∈Bn. There exist g,h∈Bn such that f·g=h. Assume that d≜deg⁡(h) and e≜deg⁡(g). Following the notion of fast algebraic immunity, one may just multiply f (over F2) by g of degree e, 1≤e<n/2, and get e+d by enumerating all possible (e,d).Comparatively, one can take two odd-variable Carlet-Feng functions as initial functions and construct a class of 1-resilient functions on even variables by the method proposed in [19].Thus we can determine the appropriate values of(e,d) for the three classes of Boolean functions, the first two by Carlet-Feng method [9] and the method in [19], respectively, and the last one from the method proposed in Section 3. Implemented via Maple language, Table 1 presents the minimal values of (e,d) for the functions on even variables (from 6 to 16). In the table, the last column takes (s,m,u,v)=(0,2k-1,1,2k-1-1).Table 1
Fast algebraic immunities of three classes of functions.
n
Carlet-Feng Functions [9]
Functions by [19]
The Proposed construction
6
5
5
5
8
6
6
7
10
9
9
9
12
10
10
11
14
13
12
13
16
15
14
15One can check that whenn = 8, 12, 14, and 16, the minimal values of (e,d) by the proposed method are closer to the bounds (i.e.,n) than those in [19]. In fact, when n=8 and 12, the results by our method are even better than those by Carlet-Feng functions [9], which makes the resistance against fast algebraic attack emerge stronger.Moreover, one can find that, for all the(e,d) of the last column, we have e+d≥n-1. Combining this with the results in the previous section, we may expect that the functions constructed by the proposed method are almost perfect algebraic immune.


## 7. Conclusion

Based on bivariate representation over finite field, the paper constructed a class of 1-resilient Boolean functions on even variables with almost perfect algebraic immunity. The resulting construction can resist algebraic attack and fast algebraic attack almost perfectly along with corresponding immunity against correlation attack.We mention that it is expected for the cryptographic community to construct Boolean function with as much cryptographic properties as possible. A natural but interesting question is how to extend the proposed construction to other important cryptographic properties such as algebraic degree and nonlinearity. We leave it as a future work.



---

*Source: 6268230-2017-09-14.xml*