
Research Article


Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity 

Belmeguenai Aissa
and
Doghman Nouredine



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





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 tradeoffs involved among the
above properties. For example, Siegenthaler showed (Siegenthaler, 1984) that
for an nvariable Boolean function f cannot at the same time have a high degree
and a high order of correlation immunity. If the function f is kth order correlation
immune function (0 ≤ k
n) then f has algebraic degree smaller than or equal to nk. Moreover, if fis
kresilient with k≤n2, then d° (f) = nk1. The exact nature of tradeoff
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 nvariable kresilient function, with k≤n2: 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 nvariable, kresilient
function is upper bounded by 2^{n1}2^{k+1}. Tarannikov showed
that resilient functions achieving this bound must have degree nk1 (that is,
achieve Siegenthaler’s bound); thus, they achieve best possible tradeoffs
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 tradeoff 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 tradeoffs 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 nvariable 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 nvariable
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 WalshHadamard transform (or spectrum) of f is defined as
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:
Proposition 2: (Xiao and Massey, 1988): Let f a Boolean function on
.
Then f is tth order correlationimmune if and only if .It
is tth 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 nvariable function, kresilient 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
The Walsh transform of g is
Proposition 3: Let f and h be two Boolean functions on .
Then
• 
If f and h are tresilient, then function g defined by (3)
is tresilient; 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;
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 tresilient functions on and
let h_{1} and h_{2} be two kresilient 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 
• 
The function g is (t + k + 1)resilient. 
• 
The nonlinearity of g is satisfied 
• 
If the Walsh transform of h_{1} and h_{2}
have disjoint supports, then, we have 
• 
If the Walsh transforms of f_{1} and f_{2}
have disjoint supports, as well as of h_{1} and h_{2}, then 
• 
If f_{1} and f_{2} are distinct and if h_{1}
and h_{2} are distinct, then algebraic degree of g equals: 
• 
If f_{1} and f_{2} are two rvariables tresilient
having disjoint spectra, achieving a 2^{r¯1}  2^{t+1}
nonlinearity, if h_{1} and h_{2} are two svariables kresilient
having disjoint spectra, achieving a 2^{s¯1}2^{k+1}
nonlinearity and such that d° (f_{1} + f_{2}) = rt1,
d° (h_{1} + h_{2}) = sk1, then g is a (r + s)variable
and (t + k+ 1)resilient with a r+stk2 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
tresilient functions on
and let h_{1}, h_{2}, h_{3}, h_{1} and h_{4}
be four kresilient functions on .
Consider the function
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 tresilient and if h_{1}, h_{2}, h_{3} and h_{4}
be four kresilient, 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
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 tresilient
and if h_{1}, h_{2}, h_{3}, h_{4} are kresilient,
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: 
• 
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: 
• 
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: 
• 
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:
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 rvariable plateaued functions that have the same amplitude 2^{m}. Let h_{1}, h_{2}, h_{3} and h_{4} be four svariable 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
because f_{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:
then, we deduced that g is a plateaued function with amplitude 2^{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 tradeoffs 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 nvariable tresilient functions. Consider the functions g ∈ B_{n+2} such that
Where and
y_{1}, y_{2} ∈ F_{2}. Note that the truthtable
of g can be obtained by concatenating the truthtable of f and h. We have truthtables:
The Walsh transforms of g is equal:
Where and
v_{1}, v_{2} ∈ F_{2}.
Truthtables 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 tresilient, then the function g is tresilient.
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 + 1resilient.
Proof: If f and h be two functions tresilient, 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 tresilient. 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+1resilient.
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 + 1resilient, 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 + 1resilient, 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
using relation (2): This implies the inequality 2^{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 + 1resilient, 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
Using relation (2), we have also 2^{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
Using relation (2), we have Ng ≥ 2^{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 + 1resilient, 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
Using relation (2), we have 2^{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 nvariable tresilient 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 + 2variable tresilient 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} ) =
If v_{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 nvariable 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 tradeoffs between resiliency order, algebraic degree and nonlinearity (that is, achieving Siegenthaler’s bound and Sarkar et al.’s bounds).

REFERENCES 
1: Ars, G. and J.C. Faugere, 2005. Algebraic immunity of functions over finite fields. Proceedings of the Workshop on Boolean Functions: Cryptotography and Aapplication, Mar. 78, University of Rouen.
2: Camion, P., C. Carlet, P. Charpin and N. Sendrier, 1992. On Correlation Immune Functions, Advances in Cryptology. SpringerVerlag, London.
3: Carlet, C., 2001. On the coset weight divisibility and nonlinearity of resilient and correlationimmune functions. Proceedings of the Sequence and their Applications, (SETA'01), SpringerVerlag, London, pp: 131144.
4: Carlet, C. and P. Sarkar, 2002. Spectral domain analysis of correlation and resilient Boolean functions. Finite Fields Appli., 8: 120130.
5: Carlet, C., 2002. A larger class of cryptographic Boolean functions via a study of the MaioranaMc Farland construction. Proceedings of the Annual International Cryptology Conference, August 1822, 2002, Santa, Barbara, CA., pp: 549564.
6: Carlet, C., 2004. On the secondary constructions of resilient and bent functions coding, cryptography and combinatorics. Prog. Comput. Sci. Applied Logic, 23: 328.
7: 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 49, 2005, Adelaide, SA., pp: 11011105.
8: 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: 31053121. Direct Link 
9: 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 37, 1996, SpringerVerlag, London, pp: 232243.
10: 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 48, 2002, Warsaw, pp: 346359.
11: Ding, C., G. Xiao and W. Shan, 1991. The stability theory of stream ciphers, N° 561, Lecture Note in Computer Sci., Vol. 561, SpringerVerlag, London.
12: Filiol, E. and C. Fontaine, 1998. Highly nonlinear balanced Boolean functions with a good correlationimmunity. Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques, May 31June 4, 1998, Espoo, pp: 475488.
13: 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 1519, 1999, Springer Verlag, London, pp: 198215.
14: Maitra, S. and E. Pasalic, 2002. Further constructions of resilient functions with very high nonlinearity. IEEE Trans. Inform. Theory, 48: 18251834. Direct Link 
15: Maitra, S. and P. Sarkar, 2002. Modifications of patterson wideman functions for cryptographic applications. IEEE Trans. Inform. Theory, 48: 278284. Direct Link 
16: 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 26, 2004, Interlaken, pp: 474491.
17: Menezes, A.J., P.C. van Oorschot and S.A. Vanstone, 1997. Handbook of Applied Cryptography. CRC Press, New York, USA.
18: Pasalic, E., T. Johansson, S. Maitra and P. Sarkar, 2001. New construction of resilient and correlationimmune Boolean functions achieving upper bounds on nonlinearity. Elect. Notes Discrete Math., 6: 158167. Direct Link 
19: 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 1418, 2000, SpringerVerlag, London, pp: 485506.
20: Sarkar, P. and S. Maitra, 2000. Nonlinearity bounds and construction of resilient Boolean functions. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, May 1418, 2000, Springer Verlag, London, pp: 515532.
21: Seberry, J., X.M. Zhang and Y. Zheng, 1994. On constructions and nonlinearity of correlation immune Boolean functions. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, May 1214, 1994, SpringerVerlag, London, pp: 181199.
22: Siegenthaler, T., 1984. Correlationimmunity of nonlinear combining functions for cryptographic applications. IEEE Trans. Inform. Theory, 30: 776780.
23: Siegenthaler, T., 1985. Decrypting a class of stream ciphers using ciphertext only. IEEE Trans. Comput., 34: 8185.
24: Tarannikov, Y.V., 2000. On resilient Boolean functions with maxim um possible nonlinearity. Proceedings of the 1st International Conference on Progress in Cryptology, December 1013, 2000, SpringerVerlag, London, pp: 1930.
25: Tarannikov, Y.V., 2001. New construction of resilient Boolean functions with maximum nonlinearity. Proceedings of the 8th International Workshop on Fast Software Encryption, April 24, 2001, SpringerVerlag, London, pp: 6677.
26: Xiao, G.Z. and J.L. Massey, 1988. A spectral characterization of correlationimmune combining function. IEEE Trans. Theory Inform., 3: 569571.
27: Zheng, Y. and X.M. Zhang, 2000. Improving Upper Bound Cryptographic Properties, Lecture Note in Computer Science. SpringerVerlag, London, pp: 485506.



