**ABSTRACT**

In this study, we first give a survey of the Siegenthaler’s constructions and the general Carlet’s construction of resilient functions, permitting to obtain resilient functions achieving the best possible trade-offs between resiliency order, algebraic degree and nonlinearity. Then, we introduce and we study a new secondary construction of resilient functions based on the principal of the siegenthaler’s construction. This construction permitted to increase the algebraic immunity, algebraic degree and define many more resilient functions where the degree, algebraic immunity, resiliency and nonlinearity achieving are high. Thus, permits to obtain resilient functions achieving the best possible trade-offs between resiliency order, algebraic degree and nonlinearity (that is, achieving Siegenthaler’s and Sarkar, al.’s bounds). We conclude the paper by generalizing our construction to plateaued functions.

PDF Abstract XML References Citation

####
**How to cite this article**

*Journal of Applied Sciences, 7: 317-325.*

**DOI:**10.3923/jas.2007.317.325

**URL:**https://scialert.net/abstract/?doi=jas.2007.317.325

**INTRODUCTION**

In the standard model of stream cipher, the outputs to n Linear Feedback Shift Register (LFSR) are combined by a nonlinear Boolean function to produce the keystream. This keystream is bitwise XORed with the message plantext to produce the ciphertext. The decryption machinery is identical to the encryption machinery. Then it is now well accepted that for a Boolean function to be used in stream cipher systems it must satisfy several properties: balancedness, high nonlinearity, high algebraic degree and high order of correlation immunity to resist different know attacks (Siegenthaler, 1985; Menezes *et al*., 1997; Ding *et al*., 1991).

Each of the above mentioned properties provide protection against a class of attacks. Also it is not possible to get the best possible values for each of these properties spartanly and there are certain trade-offs involved among the above properties. For example, Siegenthaler showed (Siegenthaler, 1984) that for an n-variable Boolean function f cannot at the same time have a high degree and a high order of correlation immunity. If the function f is k-th order correlation immune function (0 ≤ k n) then f has algebraic degree smaller than or equal to n-k. Moreover, if fis k-resilient with k≤n-2, then d° (f) = n-k-1. The exact nature of trade-off among algebraic degree, order of correlation immunity and nonlinearity has also been investigated (Sarkar and Maitra, 2000a; Tarannikov, 2000; Zheng and Zhang, 2000; Carlet, 2001; Carlet and Sarkar, 2002). Many papers have approached the construction problem by fixing one or two parameters and trying to design balanced Boolean function with good parameters (Camion *et al*., 1992; Seberry *et al*., 1994; Chee *et al*., 1996; Filiol and Fontaine, 1998; Maitra and Sarkar, 1999; Carlet and Sarkar, 2002; Sarkar and Maitra, 2000b). Thus, only constructions interesting of optimal functions that we know are of secondary constructions type and they are based on the principe introduced by Sarkar and Maitra (2000a). Among these constructions, we can quote, for example, those of Pasalic, Maïtra, Johansson and Sarkar (Paslic *et al*., 2001) or those of Carlet (2004) who generalizes and extends the whole of the secondary constructions presented by Sarkar and Maitra (2000a), Taranikov (2000), (Taranikov (2001), Paslic *et al*. (2001), Maitra and Pasalic (2002), Maitra and Sarkar (2002) and Carlet (2002).

Sarkar and Maitra (2000b) have showed in that a divisibility bound on the Walsh transform values of an n-variable k-resilient function, with k≤n-2: these values are divisible by 2^{k+2}, also, this divisibility bound is improved in (Carlet, 2001; Carlet and Sarkar, 2002). Independently obtained by Tarannikov (2000) and by Zheng and Zhang (2001): the nonlinearity of any n-variable, k-resilient function is upper bounded by 2^{n-1}-2^{k+1}. Tarannikov showed that resilient functions achieving this bound must have degree n-k-1 (that is, achieve Siegenthaler’s bound); thus, they achieve best possible trade-offs between algebraic degree, resiliency order and nonlinearity.

Since the introduction, the cryptographic parameters: a high algebraic degree, a high resiliency order and a high nonlinearity were the only requirements needed for constructing the Boolean function used in a stream cipher or in filtering model. The recent algebraic attacks (Courtois and Meier, 2002; Meier *et al*., 2004) have dramatically complicated this situation by adding a new algebraic immunity criterion of considerable importance to this list. Very recently, a new criterion of algebraic immunity has received a lot of attention in cryptographic literature for example (Ars and Fourgère, 2005; Carlet and Gaborit, 2005; Carlet *et al*., 2006). Carlet and Gaborit (2005) showed that it was not hard to construct functions with an optimal AI and that there are strong reasons which indicate that, as soon as n is large enough, almost all random balanced Boolean functions were almost optimal.

In this research, we first study a construction combined by a Siegenthaler’s construction and Carlet’s general secondary construction permitting to obtain resilient function with best possible trade-off between algebraic degree, resiliency order and nonlinearity. Then, we introduce and we study a new construction of resilient functions on based on the principal of the Siegenthaler’s construction. These constructions permitted to increase the cryptographic parameters and to define many more resilient and plateaued functions where the degree, algebraic immunity, resiliency and nonlinearity achieving are high. Thus, permit to obtain resilient functions achieving the best possible trade-offs between resiliency order, algebraic degree and nonlinearity (that is, achieving Siegenthaler’s and Sarkar’s bounds.

**CONCEPT AND DEFINITIONS**

In this section, we introduce a few basic concepts and definitions. A Boolean function on n variables may be viewed as a mapping from in to F_{2}. The set of all n-variable Boolean function is denoted by B_{n}. By ⊕ we denote sum modulo 2. The Hamming weight wt (f) of a Boolean function f on is the size of its support . The Hamming distance d (f, g) between two Boolean functions f and g is the Hamming weight of their difference f ⊕ g, d (f, g) = wt (f ⊕ g). An n-variable Boolean function f has unique algebraic normal form (A.N.F).

The algebraic degree of Boolean function f, denoted by d°(f), is defined as the number of variables in the longest term of f. If algebraic degree of f is smaller than or equal to one then f is called affine function. An affine function with a constant term equal to zero is called a linear function.

**Definition 1**: Let f a function on . The Walsh-Hadamard transform (or spectrum) of f is defined as

(1) |

Where u.x denoted the usual scalar product of vectors u and x.

**Definition 2:** A Boolean function f on is called balanced if wt(f) = wt(f ⊕ 1). Otherwise, f is balanced if and only if wt(f) = 2^{n¯1}.

**Definition 3:** A function is called plateaued if its squared Walsh transform takes at most one nonzero value, that is, if its Walsh transform takes at most three values 0 and ±λ (where λ is some positive integer, that we call the amplitude of the plateaued function).

**Proposition 1:** Let f a Boolean function on .The nonlinearity Nf of f is equal to:

(2) |

**Proposition 2:** (Xiao and Massey, 1988): Let f a Boolean function on . Then -f is t-th order correlation-immune if and only if .It is t-th resilient if moreover .

**Definition 3:** (Carlet *et al*., 2006) Let f ∈ B_{n}. The algebraic immunity AI_{n} (f) of f is the smaller degree of non null function g such that f * g = 0 or (1 + f)* g = 0. Otherwise, the minimum value of d such that f or f + 1 admits an annihilator of degree d.

We denote by (n, k, d, N), we mean an n-variable function, k-resilient function having degree d and nonlinearity N. In the above notation, we may replace some component by (-) if we do not want to specify it.

**SECONDARY CONSTRUCTIONS IN LITERATURE **

**Siegenthaler’s construction: **The functions g ∈ B_{n} constructed by Siegenthaler are defined by the form

(3) |

The Walsh transform of g is

(4) |

**Proposition 3:** Let f and h be two Boolean functions on . Then

• | If f and h are t-resilient, then function g defined by (3) is t-resilient; moreover, if for every u ∈ of Hamming weight wt (u) = t + 1, we have Wf (u) + Wh (u) = 0, then g is (t + 1)-resilient. |

• | The nonlinearity of g is: N_{g} ≥ N_{f} + N_{h}. |

• | if f and h achieve maximum possible nonlinearity 2^{n¯1} - 2^{t+1} and if g is (t + 1)-resilient, then the nonlinearity 2^{n} - 2^{t+2} of g is the best possible; |

• | if the supports of the Walsh transforms of f and h are disjoint, then we have N_{g} = 2^{n¯1} + min (N_{f }, N_{h}); thus, if f and h achieve nonlinearity 2^{n¯1} - 2^{t+1} then g achieves best possible nonlinearity 2^{n} - 2^{t+1}. |

• | If the degree of f and h are not all the same (i.e d° (f) ≠ d° (h)), then we have: d° g = 1 + max (d° f, d° h). |

**General carlet’s construction: **In a recent study (Carlet, 2004), Carlet presented secondary constructions generalizing the Tarannikov *et al*.’s construction. The functions g ∈ B_{r+s} in which Carlet is interested are defined starting from two functions f_{1} and f_{2} on B_{r} and two functions h_{1} and h_{2} on B_{s} by the form;

(5) |

**Proposition 4:** (Carlet, 2004): Let r, s, t and k be positive integers such that t r and k s . Let f_{1} and f_{2} be two t-resilient functions on and let h_{1} and h_{2} be two k-resilient functions on . Let a function g on defined by (5). Then:

• | The value of the Walsh transform of g, for every (u, v) ∈ x equals |

(6) |

• | The function g is (t + k + 1)-resilient. |

• | The nonlinearity of g is satisfied |

(7) |

• | If the Walsh transform of h_{1} and h_{2} have disjoint supports, then, we have |

(8) |

• | If the Walsh transforms of f_{1} and f_{2} have disjoint supports, as well as of h_{1} and h_{2}, then |

(9) |

• | If f_{1} and f_{2} are distinct and if h_{1} and h_{2} are distinct, then algebraic degree of g equals: |

(10) |

• | If f_{1} and f_{2} are two r-variables t-resilient having disjoint spectra, achieving a 2^{r¯1} - 2^{t+1} nonlinearity, if h_{1} and h_{2} are two s-variables k-resilient having disjoint spectra, achieving a 2^{s¯1}-2^{k+1} nonlinearity and such that d° (f_{1} + f_{2}) = r-t-1, d° (h_{1} + h_{2}) = s-k-1, then g is a (r + s)-variable and (t + k+ 1)-resilient with a r+s-t-k-2 degree achieving a 2^{r+s¯1} - 2^{t+k+2} nonlinearity. Hence, it achieves a Siegenthaler’s and Sarkar et al’s bounds. |

**Combination between the siegenthaler’s construction and the general carlet’s construction:** Let r, s, t and k be positive integers such that t r and k s. Let f_{1}, f_{2}, f_{3} and f_{4} be four t-resilient functions on and let h_{1}, h_{2}, h_{3}, h_{1} and h_{4} be four k-resilient functions on . Consider the function

(11) |

Where such that g_{1} and g_{2} be two functions on defined as follows:

**Proposition 5:** Let a function g ∈ B_{r+s+1} defined by (11). Then, if f_{1}, f_{2}, f_{3} and f_{4} are t-resilient and if h_{1}, h_{2}, h_{3} and h_{4} be four k-resilient, then g is (t + k + 1)-resilient. Moreover, if for every of Hamming weight (t + k + 1), we have Wg_{1} (u, v) + Wg_{2} (u, v) = 0, then g is (t + k +2)-resilient. The Walsh transform of g at w∈ F_{2} takes Value

(12) |

**Proof:** For every , w∈ F_{2} and from relations 4, we have Wg (u, v, w) = Wg_{1} (u, v) + (-1)^{w} Wg_{2} (u, v), hence from Relations 6, we deduced

that is relation (12).

If f_{1}, f_{2}, f_{3}, f_{4} are t-resilient and if h_{1}, h_{2}, h_{3}, h_{4} are k-resilient, then, we have, from item (ii) of proposition 4, the functions g_{1} and g_{2} are (t + k + 1)-resilient. This implies for every of Hamming weight smaller than or equal to t + k + 1 the values of Wg_{1} (u, v) and Wg_{2} (u, v) are null, which implies the value of Wg (u, v, w) = Wg_{1} (u, v) + (-1)^{w} Wg_{2} (u, v) is null for every w∈ F_{2}. Moreover, if for every of Hamming weight (t + k + 2), the values of Wg_{1} (u, v) and Wg_{2} (u, v) satisfy the relation Wg_{1} (u, v) = - Wg_{2} (u, v). This implies = - [Wf_{3} (u) [Wh_{3} (v) + Wh_{4} (v) ] + Wf_{4} [Wh_{3} (v) - Wh_{4} (v) ]], the for w = 0, we deduce that Wg (u, v, w) = Wf_{1} (u) [Wh_{1} (v) + Wh_{2} (v) ] + Wf_{2} (u) [Wh_{1} (v) - Wh_{2} (v) ] = (-1)^{0} Wf_{3} (u) [Wh_{3} (v) + Wh_{4} (v) ] + Wf_{4} (u) [Wh_{3} (v) - Wh_{4} (v) ]]. Therefore, g is (t + k + 2)-resilient.

**Theorem 1:** Let a function g ∈ B_{r+s+1} defined by (11). Then

• | The nonlinearity of g is: |

(13) |

• | If the supports of the Walsh transform of h_{1} and h_{2} are disjoint, as well as those of h_{3} and h_{4} then we have: |

(14) |

• | If the Walsh transforms of f_{1} and f_{2} have disjoint supports, as well as of f_{3} and f_{4} and if the supports of the Walsh transform of h_{1} and h_{2} are disjoint, as well as those of h_{3} and h_{4}, then we have: |

(15) |

• | If f_{1}, f_{2} are distinct, if f_{3}, f_{4} are distinct, if h_{1}, h_{2} are distinct and if h_{3}, h_{4} are distinct then the algebraic degree of g takes:d° g = 1 + max (d° f _{1}, d° h_{1}, d° f_{3}, d° (f_{1} + f_{2}) + d° (h_{1} + h_{2}), d° (f_{3} + f_{4}) + d° (h_{3} + h_{4})).Otherwise, it takes: 1 + max (d° f _{1}, d° h_{1}, d° f_{3}, d° h_{3}). |

**Proof:**

• | Relation (12) implies |

Using relation (2)

is equivalent to (13).

• | If the supports of the Walsh transform of h_{1}, h_{2} are disjoint and if the Walsh transform of h_{3}, h_{4} have disjoint supports then relation (12) can take: |

which implies that

Using (2) we deduce

Which is equivolent (14)

• | If the Walsh transforms of f_{1} and f_{2} have disjoint supports, as well as those of f_{3}, f_{4} and if the Walsh transforms of h_{1} and h_{2} have disjoint supports, as well as those of h_{3} and h_{4}, we deduce from (12) that: |

which, using (2)

is equivalent to (15).

• | It is obvious that if f_{1}, f_{2} are distinct, if f_{3}, f_{4} are distinct, if h_{1}, h_{2} are distinct and if h_{3}, h_{4} are distinct the terms of highest degree is in (f_{1} + f_{2}) (x) (h_{1} + h_{2}) (y) or in (f_{3} + f_{4}) (x) (h_{3} + h_{4}) (y). |

**Corollary 1:** Let f_{1}, f_{2}, f_{3} and f_{4} be four (r, t, –, 2^{r¯1} – 2^{t+1}) functions and if the Walsh transforms of f_{1}, f_{2} have disjoint supports, as well as those of f_{3}, f_{4} and such that f_{1} + f_{2} and f_{3} + f_{4} have the same degree r–t–1. Let h_{1}, h_{2}, h_{3} and h_{4} be four (s, k, –, 2^{s¯1}– 2^{k+1}) functions and if the Walsh transforms of h_{1}, h_{2} have disjoint supports, as well as those of h_{3}, h_{4} and such that h_{1} + h_{2} and h_{3}, h_{4} have the same degree s–k–1, then the function g ∈ B_{r+s+1} defined by 11 is (t+ k + 2)-resilient has degree r + s – t – k – 2 and nonlinearity 2^{r+s} – 2^{t+k+3} and thus, achieves Siegenthaler’s and Sarkar *et al*.’s bounds.

**Construction of plateaued functions:** We consider now the same construction as in the section 4, but applied to plateaued functions instead of resilient functions.

**Lemma 1:** Let r, s be two positive integers. Let f_{1}, f_{2}, f_{3} and f_{4} be four r-variable plateaued functions that have the same amplitude 2^{m}. Let h_{1}, h_{2}, h_{3} and h_{4} be four s-variable plateaued functions that have the same amplitude 2^{l}. Let the function g (r + s + 1)-variable defined by (11).

• | If for every , the values of Wf_{1} (u), Wf_{2} (u), Wf_{3} (u) and Wf_{4} (u) and if for every , the values of Wh_{1} (v), Wh_{2} (v), Wh_{3} (v) and Wh_{4} (v) are simultaneously null, or simultaneously non null, then g is a plateaued function with amplitude 2^{m+l+1}. |

• | If the Walsh transforms of f_{1} and f_{2} have disjoint supports, as well as of f_{3} and f_{4} and if the supports of the Walsh transform of h_{1} and h_{2} are disjoint, as well as those of h_{3} and h_{4}, then g is a plateaued function with amplitude 2^{m+l}. |

**Proof:**

• | From relation (10), we deduced if the functions Wf_{1}, Wf_{2}, Wf_{3}, Wf_{4}, Wh_{1}, Wh_{2}, Wh_{3} and Wh_{4} are simultaneously null (resp. Simultaneously non null), then Wg (u, v, w) is null (resp. equal _{1}, f_{2}, f_{3}, f_{4}, are plateaued functions with the same amplitude 2^{m} and h_{1}, h_{2}, h_{3}, h_{4}, are plateaued functions having the same amplitude 2^{l}: then, g is a plateaued function with amplitude 2^{m+l+1}. |

• | If the Walsh transforms of f_{1} and f_{2} have disjoint supports, as well as of f_{3} and f_{4} and if the supports of the Walsh transform of h_{1} and h_{2} are disjoint, as well as those of h_{3} and h_{4}, then, from relation (10), we have Wg (u, v, w) is equal 0 or equal: ^{m+l}. |

**A new secondary construction of resilient functions: **In this section, we present a new secondary construction of resilient functions on based on the Siegenthaler’s construction principle, permitting to obtain resilient functions achieving the best possible trade-offs between resiliency order, algebraic degree, immunity algebraic degree and nonlinearity (that is, achieving Siegenthaler’s and Sarkar’s *et al*. bound).

Let n, t be positive integers such that t n and let f and h be two n-variable t-resilient functions. Consider the functions g ∈ B_{n+2} such that

(16) |

Where and y_{1}, y_{2} ∈ F_{2}. Note that the truth-table of g can be obtained by concatenating the truth-table of f and h. We have truth-tables:

The Walsh transforms of g is equal:

(17) |

Where and v_{1}, v_{2} ∈ F_{2}.

Truth-tables of Walsh transform g is:

The goal of proposition 6 and theorem 2 are to show, while being based on relation 17, how the resiliency and non linearity of g are related to the comportment of the functions f and h.

**Proposition 6: **Let g ∈ B_{n+2} be a function defined by 16. Then, if f and h be two functions t-resilient, then the function g is t-resilient. Moreover, if for every of Hamming weight t + 1, we have Wf (u) = Wh (u) or Wh (u) = – 3Wf (u), then the function g is a t + 1-resilient.

**Proof: ** If f and h be two functions t-resilient, then for every of Hamming weight smaller than or equal to t, the values of Wf (u), Wh (u) are null and it is deduced that the value Wg (u, v1, v2) =

is null for every : The functions g is t-resilient. Moreover, if for every of Hamming weight t+1, we have the values Wf (u), Wh (u) satisfy, respectively the relations Wh (u) – Wf (u) = 0, then for v_{1} ≠ v_{2} = 1, or 3Wf (u)+Wh (u) = 0, then for v_{1} = v_{2} = 0. We have Wg (u, v_{1}, v_{2}) = 0 it is deduced that the functions g is a t+1-resilient.

**Theorem 2: **Let g ∈ B_{n+2} be a function defined by 16.

• | If for every all pair (v_{1}, v_{2}) ∈ F_{2} x F_{2} such that v_{1} = v_{2} = 0, then the non linearity of g is obtained from those of f and h in the following way:(18) Ng ≥ 3NF + Nh. Moreover, if f and h achieve a maximum possible 2 ^{n¯1} – 2^{t+2} nonlinearity and if g is t + 1-resilient, then the nonlinearity 2^{n+1} – 2^{t+2} of g is the best possible. If the support of the Walsh transform of f and h are disjoint, then we have(19) Ng = 2 ^{n¯1} + min (3Nf, 2^{n} + Nh); thus, if f and h achieve a maximum possible 2^{n¯1} – 2^{t+2} nonlinearity, then g achieves a maximum possible 2^{n+1} – 3x2^{t+1} nonlinearity. |

• | If for every all pair (v_{1}, v_{2}) ∈ F_{2} x F_{2} such that v_{1} ≠ v_{2} or v_{1} = v_{2} = 1, we have(20) Ng ≥ 2 ^{n} + Nf + Nh. Moreover, if f and h achieve a maximum possible 2^{n¯1} – 2^{t+2} nonlinearity and if g is t + 1-resilient, then the nonlinearity 2^{n+1} – 2^{t+2} of g is the best possible. If the support of the Walsh transform of f and h are disjoint, then we have (21) Ng = 3x2 ^{n¯1} + min (nf, Nh); thus, if f and h achieve a maximum possible 2^{n¯1}–2^{t+1} nonlinearity, then g achieves maximum possible nonlinearity 2^{n+1}–2^{t+1}. |

• | If the monomials of highest degree in the algebraic normal forms of f and h are not all the same (i.e. d° f ≠ d° h), then d° g = 2 + max (d° f, d° h). |

**Proof:**

• | If for every all pair (v_{1}, v_{2}) ∈ F_{2} x F_{2} such that v_{1} = v_{2} = 0, then we deduced from relation (17) the number ^{n+2} – 2Ng ≤ 3 x (2^{n} – 2Nf) + 2^{n} – 2Nh. We deduce that Ng ≥ 3Nf + Nh. Moreover if Nf = Nh = 2^{n¯1} – 2^{t+1}, then from relation (18), we have Ng ≥ 2^{n¯1} – 2^{t+3} and if g is a t + 1-resilient, then from we have Ng ≤ 2^{n+1} – 2^{t+2}: we deduce that the 2^{n+1} – 2^{t+2} nonlinearity of g is the best possible. If the support of the Walsh transform of f and h are disjoint, we deduce also, from the relation (17), that the number is equal to ^{n+2} – 2Ng = min (3 x (2^{n} – 2Nf), 2^{n} – 2Nh) and Ng are equals. Therefore Ng = 2^{n¯1} + min (3Nf, 2^{n} + Nh). Thus, if f and h achieve a 2^{n¯1} – 2^{t+1} nonlinearity then from the relation (19), it is clearly that g achieves a maximum possible 2^{n¯1 – }3 x 2^{t+1} nonlinearity. |

• | If for every all pair (v_{1}, v_{2}) ∈ F_{2} x F_{2} such that v_{1} ≠ v_{2} or v_{1} = v_{2} = 1, then we deduce from relation (17) that ^{n} + Nf + Nh. Moreover if f and h achieve a 2^{n¯1} – 2^{t+1} nonlinearity, then from the relation (20), we deduce Ng≥2^{n+1}–2^{t+2} and if g is a t + 1-resilient, then from we have Ng ≥2^{n+1}–2^{t+2}: we deduce then that the 2^{n+1}–2^{t+2} nonlinearity of g is the best possible. If the support of the Walsh transform of f and h are disjoint, we deduce also from relation (17) that ^{n+2} – 2Ng = Min (2^{n} – 2Nf, 2^{n} – 2Nh) if f and h achieve a maximum possible 2^{n¯1} – 2^{t+1} nonlinearity and then from the relation (20) we have 2^{n+1} – 2^{t+1} | ||

• | It is obvious that it d° g = 2 + max (d° f, d° h). |

**Corollary 2:** Let f and h be two n-variable t-resilient functions with disjoint Walsh supports achieving a 2^{n¯1} – 2^{t+1} nonlinearity such that d° (f + h) = n – t – 1 and if for every all pair (v_{1}, v_{2}) ∈ F_{2} x F_{2} such that v_{1} ≠ v_{2} or v_{1} = v_{2} = 1. Then the function defined by 16 is n + 2-variable t-resilient function has a n – t + 1 degree and having a 2^{n+1} – 2^{t+1} nonlinearity that is achieving Siegenthaler’s and Sarkar *et al*’s bounds; note that this construction increases by 2 the degree.

**Construction of plateaued functions: **We consider now the same construction 16, but applied to plateaued functions instead of resilient functions.

**Lemma 2: **Let n be positive integer. Let f and h be two plateaued functions having the same amplitude 2^{r} on . Let g ∈ B_{n+2} be function given by 16 then:

• | If for every all pair (v_{1}, v_{2}) ∈ F_{2} x F_{2} such that v_{1} = v_{2} = 0 and if for every the values of Wf (u) and Wh (u) are simultaneously null, or simultaneously non null, then g is plateaued function with amplitude 2^{r+2} on . |

• | If for every all pair (v_{1}, v_{2}) ∈ F_{2} x F_{2} such that v_{1} ≠ v_{2} or v_{1} = v_{2} = 1 and if at least one of the values Wf (u) and Wf (u) is null, then g is a plateaued function with an amplitude 2^{r} on . |

**Proof:**

• | For every and for all pair (v_{1}, v_{2}) ∈ F_{2} x F_{2} we have Wg(u,v_{1} ,v_{2} ) = _{1} = v_{2} = 0 and if f and h are simultaneously null (resp. Simultaneously non null), we deduce that Wg (u, v_{1}, v_{2}) is equal to 3 x (±2^{r}) + ±2^{r+2} because f and h are plateaued functions with amplitude 2^{r}: g is a plateaued function with amplitude 2^{r+2}. | |

• | If for every all pair (v_{1}, v_{2}) ∈ F_{2} x F_{2} such that v_{1} ≠ v_{2} or v_{1} = v_{2} = 1 and if at least one of the values Wf (u) and Wf (u) is null, then also from the relation (17) we have (u, v_{1}, v_{2}) = ±2^{r} because f and h are plateaued functions with an amplitude 2^{r}. |

**Proposition 7:** Let f and h be two n-variable functions with algebraic immunity AI_{n} (f) = d_{1} and AI_{n} (h) = d_{2}. Let g ∈ B_{n+2} be function given by 16 Then:

• | If d_{1} ≠ d_{2} the Ai_{n+2} (g) = 2 + min {d_{1}, d_{2}}. |

• | If d_{1} = d_{2} = d then d ≤ AI_{n+2} (g) ≤ d + 2, and AI_{n+2} (g) = d if only if there exist f_{1} and h_{1} ∈ B_{n}with algebraic degree d such that {f * f_{1} = 0, h * h_{1} = o} or {(1 + f) * f_{1} = 0, (1 + h) * h_{1} = 0} and d° g (f_{1 }+ h_{1}) ≤ d – 2. |

**Proof: **Let φ ∈ B_{n}, by LDA_{n} (φ) we denoted the set of a non null function φ_{1} ∈ B_{n} with lowest possible degree such that φ * φ_{1} = 0 or (1 + φ) * φ_{1} = 0.

• | First time we prove item i. Let us write φ = (1 +y_{1}y_{2}) φ_{1} + y_{1}y_{2}φ_{2} ∈ LDA_{n+2} (g). We first consider the case g * φ = 0. This implies (1 + y_{1}y_{2}) f * φ_{1} + y_{1}y_{2} h*φ_{2} = 0. So f * φ_{1} and h * φ_{1} = 0. Similarly for the case with (1 + g) * φ = 0. Thus, we have (1 + y_{1}y_{2}) * (1 + f) * φ_{1} + y_{1}y_{2} *(1 = h) * φ_{2} = 0. We deduce that (1 + y_{1}y_{2}) * (1 + f) * φ_{1} = 0 and y_{1}y_{2} *(1 + h) * φ_{2} = 0. Now there can be three cases in both scenarios: |

• | φ_{1} is zero and φ_{2} is non zero. So d° (φ_{2}) ≥ d_{2}. This implies d° (g) ≥ d_{2} + 2 | |

• | φ_{1} is non zero and φ_{2} is zero. So d° (φ_{1}) ≥ d_{1}. This implies d° (g) ≥ d_{1} + 2 | |

• | φ_{1} and φ_{2} are non zero. So d° (φ_{1}) ≥ d_{1} and d° (φ_{2}) ≥ d_{2}. This implies d° (g) ≥ 2 + max {d_{1}, d_{2}}. when d_{1} ≠ d_{2} |

Let f_{1} ∈ LDA_{n} (f), h ∈ LDA_{n} (h). If f * f = 0 then we have (1 + y_{1}y_{2}) f_{1} * g = 0.

If h * h_{1} = 0 then y_{1}y_{2}h_{1} * g = 0. Thus if (1 + f) * f_{1} = 0 then we have (1 + y_{1}y_{2}) f_{1} * (1+g) = 0. If (1 + h) * h = 0 then y_{1}y_{2} * h_{1} * (1 + g) = 0. We deduce that

From equation (I) and (II) we deduce that Ai_{n+2} (g) ≤ 2 + min {d_{1}, d_{2}}.

Let φ = f_{1} + y_{1}y_{2} (f_{1} + h_{2}) ∈ LDA_{n+2} (g). It is clearly that φ has at least a degree d because f, h has at least a degree d. So d ≤ Ai_{n+2} (g) ≤ d + 2.

If Ai_{n+2} (g) = d, then the highest degree term of f_{1} and h_{1} must be the same which gives d° (f_{1} + h_{2}) ≤ d – 2. Note that we have {f * f = 0, h * h = 0} or {(1 + f) * f = 0, (1 + h) * h = 0 } and d° g (f_{1} + h_{1}) ≤ d – 2. Then clearly Ai_{n+2} (g) = d.

**CONCLUSIONS**

We have given a new secondary construction of resilient functions based on the Siegenthaler’s construction principal. These constructions permit to increase the cryptographic parameters (algebraic immunity, algebraic degree, resiliency and nonlinearity) and to define many more resilient and plateaued functions where the achieved degree, algebraic immunity, resiliency and nonlinearity are high. Thus, it permits to build resilient functions achieving the best possible trade-offs between resiliency order, algebraic degree and nonlinearity (that is, achieving Siegenthaler’s bound and Sarkar *et al*.’s bounds).

####
**REFERENCES**

- Carlet, C., 2002. A larger class of cryptographic Boolean functions via a study of the Maiorana-Mc Farland construction. Proceedings of the Annual International Cryptology Conference, August 18-22, 2002, Santa, Barbara, CA., pp: 549-564.

Direct Link - Carlet, C. and P. Gaborit, 2005. On the construction of balanced Boolean functions with a goode algebraic immunity. Proceedings of the International Symposium on Information Theory, September 4-9, 2005, Adelaide, SA., pp: 1101-1105.

CrossRef - Carlet, C, D.K. Dalai, K.C. Gupta and S. Maitra, 2006. Algebraic immunity for cryptographically significant Boolean functions: Analysis and construction. IEEE Trans. Inform. Theory, 57: 3105-3121.

Direct Link - Chee, L.S., D. Lee and S.H. Sung, 1996. On the correlation immune functions and their nonlinearity. Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, November 3-7, 1996, Springer-Verlag, London, pp: 232-243.

Direct Link - Courtois, N. and W. Meier, 2002. Algebraic attacks on stream ciphers with linear feedback. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, May 4-8, 2002, Warsaw, pp: 346-359.

Direct Link - Filiol, E. and C. Fontaine, 1998. Highly nonlinear balanced Boolean functions with a good correlation-immunity. Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques, May 31-June 4, 1998, Espoo, pp: 475-488.

Direct Link - Maitra, S. and P. Sarkar, 1999. Highly nonlinear resilient functions optimizing Siegenthaler=s inequality. Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, August 15-19, 1999, Springer Verlag, London, pp: 198-215.

Direct Link - Maitra, S. and E. Pasalic, 2002. Further constructions of resilient functions with very high nonlinearity. IEEE Trans. Inform. Theory, 48: 1825-1834.

Direct Link - Maitra, S. and P. Sarkar, 2002. Modifications of patterson- wideman functions for cryptographic applications. IEEE Trans. Inform. Theory, 48: 278-284.

Direct Link - Meier, W., E. Pasalic and C. Carlet, 2004. Algebraic attacks and decomposition of Boolean functions. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, May 2-6, 2004, Interlaken, pp: 474-491.

Direct Link - Pasalic, E., T. Johansson, S. Maitra and P. Sarkar, 2001. New construction of resilient and correlation-immune Boolean functions achieving upper bounds on nonlinearity. Elect. Notes Discrete Math., 6: 158-167.

Direct Link - Sarkar, P. and S. Maitra, 2000. Construction of nonlinearity Boolean function with important cryptographic properties. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, May 14-18, 2000, Springer-Verlag, London, pp: 485-506.

Direct Link - Tarannikov, Y.V., 2000. On resilient Boolean functions with maxim um possible nonlinearity. Proceedings of the 1st International Conference on Progress in Cryptology, December 10-13, 2000, Springer-Verlag, London, pp: 19-30.

Direct Link