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.
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
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 2k+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 2n-1-2k+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
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
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
| (1) |
Where u.x denoted the usual scalar product of vectors u and x.
Definition 2: A Boolean function f on
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
| (2) |
Proposition 2: (Xiao and Massey, 1988): Let f a Boolean function on
Definition 3: (Carlet et al., 2006) Let f ∈ Bn. The algebraic immunity AIn (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 ∈ Bn 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
| • | If f and h are t-resilient, then function g defined by (3)
is t-resilient; moreover, if for every u ∈ |
| • | The nonlinearity of g is: Ng ≥ Nf + Nh. |
| • | if f and h achieve maximum possible nonlinearity 2n¯1 - 2t+1 and if g is (t + 1)-resilient, then the nonlinearity 2n - 2t+2 of g is the best possible; |
| • | if the supports of the Walsh transforms of f and h are disjoint, then we have Ng = 2n¯1 + min (Nf , Nh); thus, if f and h achieve nonlinearity 2n¯1 - 2t+1 then g achieves best possible nonlinearity 2n - 2t+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 ∈ Br+s in which Carlet is interested are defined starting from two functions f1 and f2 on Br and two functions h1 and h2 on Bs by the form;
| (5) |
Proposition 4: (Carlet, 2004): Let r, s, t and k be positive integers
such that t
| • | The value of the Walsh transform of g, for every (u, v) ∈
|
| (6) |
| • | The function g is (t + k + 1)-resilient. |
| • | The nonlinearity of g is satisfied |
| (7) |
| • | If the Walsh transform of h1 and h2 have disjoint supports, then, we have |
| (8) |
| • | If the Walsh transforms of f1 and f2 have disjoint supports, as well as of h1 and h2, then |
| (9) |
| • | If f1 and f2 are distinct and if h1 and h2 are distinct, then algebraic degree of g equals: |
| (10) |
| • | If f1 and f2 are two r-variables t-resilient having disjoint spectra, achieving a 2r¯1 - 2t+1 nonlinearity, if h1 and h2 are two s-variables k-resilient having disjoint spectra, achieving a 2s¯1-2k+1 nonlinearity and such that d° (f1 + f2) = r-t-1, d° (h1 + h2) = 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 2r+s¯1 - 2t+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
| (11) |
Where
Proposition 5: Let a function g ∈ Br+s+1 defined by
(11). Then, if f1, f2, f3 and f4
are t-resilient and if h1, h2, h3 and h4
be four k-resilient, then g is (t + k + 1)-resilient. Moreover, if for every
| (12) |
Proof: For every
that is relation (12).
If f1, f2, f3, f4 are t-resilient
and if h1, h2, h3, h4 are k-resilient,
then, we have, from item (ii) of proposition 4, the functions g1
and g2 are (t + k + 1)-resilient. This implies for every
Theorem 1: Let a function g ∈ Br+s+1 defined by (11). Then
| • | The nonlinearity of g is: |
| (13) |
| • | If the supports of the Walsh transform of h1 and h2 are disjoint, as well as those of h3 and h4 then we have: |
| (14) |
| • | If the Walsh transforms of f1 and f2 have disjoint supports, as well as of f3 and f4 and if the supports of the Walsh transform of h1 and h2 are disjoint, as well as those of h3 and h4, then we have: |
| (15) |
| • | If f1, f2 are distinct, if f3,
f4 are distinct, if h1, h2 are distinct
and if h3, h4 are distinct then the algebraic degree
of g takes: d° g = 1 + max (d° f1, d° h1, d° f3, d° (f1 + f2) + d° (h1 + h2), d° (f3 + f4) + d° (h3 + h4)). Otherwise, it takes: 1 + max (d° f1, d° h1, d° f3, d° h3). |
Proof:
| • | Relation (12) implies |
Using relation (2)
is equivalent to (13).
| • | If the supports of the Walsh transform of h1, h2 are disjoint and if the Walsh transform of h3, h4 have disjoint supports then relation (12) can take: |
which implies that
Using (2) we deduce
Which is equivolent (14)
| • | If the Walsh transforms of f1 and f2 have disjoint supports, as well as those of f3, f4 and if the Walsh transforms of h1 and h2 have disjoint supports, as well as those of h3 and h4, we deduce from (12) that: |
which, using (2)
is equivalent to (15).
| • | It is obvious that if f1, f2 are distinct, if f3, f4 are distinct, if h1, h2 are distinct and if h3, h4 are distinct the terms of highest degree is in (f1 + f2) (x) (h1 + h2) (y) or in (f3 + f4) (x) (h3 + h4) (y). |
Corollary 1: Let f1, f2, f3 and f4 be four (r, t, –, 2r¯1 – 2t+1) functions and if the Walsh transforms of f1, f2 have disjoint supports, as well as those of f3, f4 and such that f1 + f2 and f3 + f4 have the same degree r–t–1. Let h1, h2, h3 and h4 be four (s, k, –, 2s¯1– 2k+1) functions and if the Walsh transforms of h1, h2 have disjoint supports, as well as those of h3, h4 and such that h1 + h2 and h3, h4 have the same degree s–k–1, then the function g ∈ Br+s+1 defined by 11 is (t+ k + 2)-resilient has degree r + s – t – k – 2 and nonlinearity 2r+s – 2t+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 f1, f2, f3 and f4 be four r-variable plateaued functions that have the same amplitude 2m. Let h1, h2, h3 and h4 be four s-variable plateaued functions that have the same amplitude 2l. Let the function g (r + s + 1)-variable defined by (11).
| • | If for every |
| • | If the Walsh transforms of f1 and f2 have disjoint supports, as well as of f3 and f4 and if the supports of the Walsh transform of h1 and h2 are disjoint, as well as those of h3 and h4, then g is a plateaued function with amplitude 2m+l. |
Proof:
| • | From relation (10), we deduced if the functions Wf1,
Wf2, Wf3, Wf4, Wh1, Wh2,
Wh3 and Wh4 are simultaneously null (resp. Simultaneously
non null), then Wg (u, v, w) is null (resp. equal
|
| • | If the Walsh transforms of f1 and f2
have disjoint supports, as well as of f3 and f4
and if the supports of the Walsh transform of h1 and h2
are disjoint, as well as those of h3 and h4, then,
from relation (10), we have Wg (u, v, w) is equal 0 or equal:
|
A new secondary construction of resilient functions: In this section,
we present a new secondary construction of resilient functions on
Let n, t be positive integers such that t
| (16) |
Where
The Walsh transforms of g is equal:
| (17) |
Where
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 ∈ Bn+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
Proof: If f and h be two functions t-resilient, then for every
is null for every
Theorem 2: Let g ∈ Bn+2 be a function defined by 16.
| • | If for every all pair (v1, v2) ∈
F2 x F2 such that v1 = v2 =
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 2n¯1 – 2t+2 nonlinearity and if g is t + 1-resilient, then the nonlinearity 2n+1 – 2t+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 = 2n¯1 + min (3Nf, 2n + Nh); thus, if f and h achieve a maximum possible 2n¯1 – 2t+2 nonlinearity, then g achieves a maximum possible 2n+1 – 3x2t+1 nonlinearity. |
| • | If for every all pair (v1, v2) ∈
F2 x F2 such that v1 ≠ v2 or v1 = v2 = 1, we have (20) Ng ≥ 2n + Nf + Nh. Moreover, if f and h achieve a maximum possible 2n¯1 – 2t+2 nonlinearity and if g is t + 1-resilient, then the nonlinearity 2n+1 – 2t+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 = 3x2n¯1 + min (nf, Nh); thus, if f and h achieve a maximum possible 2n¯1–2t+1 nonlinearity, then g achieves maximum possible nonlinearity 2n+1–2t+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 (v1, v2) ∈
F2 x F2 such that v1 = v2 =
0, then we deduced from relation (17) the number
|
| • | If for every all pair (v1, v2) ∈
F2 x F2 such that v1 ≠ v2
or v1 = v2 = 1, then we deduce from relation (17)
that
|
||
| • | 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 2n¯1 – 2t+1 nonlinearity such that d° (f + h) = n – t – 1 and if for every all pair (v1, v2) ∈ F2 x F2 such that v1 ≠ v2 or v1 = v2 = 1. Then the function defined by 16 is n + 2-variable t-resilient function has a n – t + 1 degree and having a 2n+1 – 2t+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 2r on
| • | If for every all pair (v1, v2) ∈
F2 x F2 such that v1 = v2 =
0 and if for every |
| • | If for every all pair (v1, v2) ∈ F2 x
F2 such that v1 ≠ v2 or v1 =
v2 = 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 2r on |
Proof:
| • | For
every | |
| • | If for every all pair (v1, v2) ∈ F2 x F2 such that v1 ≠ v2 or v1 = v2 = 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, v1, v2) = ±2r because f and h are plateaued functions with an amplitude 2r. |
Proposition 7: Let f and h be two n-variable functions with algebraic immunity AIn (f) = d1 and AIn (h) = d2. Let g ∈ Bn+2 be function given by 16 Then:
| • | If d1 ≠ d2 the Ain+2 (g) = 2 + min {d1, d2}. |
| • | If d1 = d2 = d then d ≤ AIn+2 (g) ≤ d + 2, and AIn+2 (g) = d if only if there exist f1 and h1 ∈ Bnwith algebraic degree d such that {f * f1 = 0, h * h1 = o} or {(1 + f) * f1 = 0, (1 + h) * h1 = 0} and d° g (f1 + h1) ≤ d – 2. |
Proof: Let φ ∈ Bn, by LDAn (φ) we denoted the set of a non null function φ1 ∈ Bn with lowest possible degree such that φ * φ1 = 0 or (1 + φ) * φ1 = 0.
| • | First time we prove item i. Let us write φ = (1 +y1y2) φ1 + y1y2φ2 ∈ LDAn+2 (g). We first consider the case g * φ = 0. This implies (1 + y1y2) f * φ1 + y1y2 h*φ2 = 0. So f * φ1 and h * φ1 = 0. Similarly for the case with (1 + g) * φ = 0. Thus, we have (1 + y1y2) * (1 + f) * φ1 + y1y2 *(1 = h) * φ2 = 0. We deduce that (1 + y1y2) * (1 + f) * φ1 = 0 and y1y2 *(1 + h) * φ2 = 0. Now there can be three cases in both scenarios: |
| • | φ1 is zero and φ2 is non zero. So d° (φ2) ≥ d2. This implies d° (g) ≥ d2 + 2 | |
| • | φ1 is non zero and φ2 is zero. So d° (φ1) ≥ d1. This implies d° (g) ≥ d1 + 2 | |
| • | φ1 and φ2 are non zero. So d° (φ1) ≥ d1 and d° (φ2) ≥ d2. This implies d° (g) ≥ 2 + max {d1, d2}. when d1 ≠ d2 |
Let f1 ∈ LDAn (f), h ∈ LDAn (h). If f * f = 0 then we have (1 + y1y2) f1 * g = 0.
If h * h1 = 0 then y1y2h1 * g = 0. Thus if (1 + f) * f1 = 0 then we have (1 + y1y2) f1 * (1+g) = 0. If (1 + h) * h = 0 then y1y2 * h1 * (1 + g) = 0. We deduce that
From equation (I) and (II) we deduce that Ain+2 (g) ≤ 2 + min {d1, d2}.
Let φ = f1 + y1y2 (f1 + h2) ∈ LDAn+2 (g). It is clearly that φ has at least a degree d because f, h has at least a degree d. So d ≤ Ain+2 (g) ≤ d + 2.
If Ain+2 (g) = d, then the highest degree term of f1 and h1 must be the same which gives d° (f1 + h2) ≤ d – 2. Note that we have {f * f = 0, h * h = 0} or {(1 + f) * f = 0, (1 + h) * h = 0 } and d° g (f1 + h1) ≤ d – 2. Then clearly Ain+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).