Subscribe Now Subscribe Today
Research Article
 

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



Belmeguenai Aissa and Doghman Nouredine
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
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.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Belmeguenai Aissa and Doghman Nouredine, 2007. Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity. 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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity 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 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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity 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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity in to F2. The set of all n-variable Boolean function is denoted by Bn. By ⊕ we denote sum modulo 2. The Hamming weight wt (f) of a Boolean function f on Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity is the size of its support Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity. 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).

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

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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity. The Walsh-Hadamard transform (or spectrum) of f is defined as

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(1)

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

Definition 2: A Boolean function f on Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity is called balanced if wt(f) = wt(f ⊕ 1). Otherwise, f is balanced if and only if wt(f) = 2n¯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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity.The nonlinearity Nf of f is equal to:

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(2)

Proposition 2: (Xiao and Massey, 1988): Let f a Boolean function on Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity. Then -f is t-th order correlation-immune if and only if Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity.It is t-th resilient if moreover .Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity

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

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(3)

The Walsh transform of g is

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(4)

Proposition 3: Let f and h be two Boolean functions on Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity. Then

If f and h are t-resilient, then function g defined by (3) is t-resilient; moreover, if for every u ∈ Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity 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: 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;

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(5)

Proposition 4: (Carlet, 2004): Let r, s, t and k be positive integers such that t Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity r and k Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity s . Let f1 and f2 be two t-resilient functions on Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunityand let h1 and h2 be two k-resilient functions on Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity. Let a function g on Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunitydefined by (5). Then:

The value of the Walsh transform of g, for every (u, v) ∈ Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity x Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunityequals

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(6)

The function g is (t + k + 1)-resilient.
The nonlinearity of g is satisfied

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(7)

If the Walsh transform of h1 and h2 have disjoint supports, then, we have

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(8)

If the Walsh transforms of f1 and f2 have disjoint supports, as well as of h1 and h2, then

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(9)

If f1 and f2 are distinct and if h1 and h2 are distinct, then algebraic degree of g equals:

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity r and k Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity s. Let f1, f2, f3 and f4 be four t-resilient functions on Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity and let h1, h2, h3, h1 and h4 be four k-resilient functions on Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity. Consider the function

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(11)

Where Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity such that g1 and g2 be two functions on Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunitydefined as follows:

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

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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunityof Hamming weight (t + k + 1), we have Wg1 (u, v) + Wg2 (u, v) = 0, then g is (t + k +2)-resilient. The Walsh transform of g at Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity w∈ F2 takes Value

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(12)

Proof: For every Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity, w∈ F2 and from relations 4, we have Wg (u, v, w) = Wg1 (u, v) + (-1)w Wg2 (u, v), hence from Relations 6, we deduced

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

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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunityof Hamming weight smaller than or equal to t + k + 1 the values of Wg1 (u, v) and Wg2 (u, v) are null, which implies the value of Wg (u, v, w) = Wg1 (u, v) + (-1)w Wg2 (u, v) is null for every w∈ F2. Moreover, if for every Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunityof Hamming weight (t + k + 2), the values of Wg1 (u, v) and Wg2 (u, v) satisfy the relation Wg1 (u, v) = - Wg2 (u, v). This implies Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity = - [Wf3 (u) [Wh3 (v) + Wh4 (v) ] + Wf4 [Wh3 (v) - Wh4 (v) ]], the for w = 0, we deduce that Wg (u, v, w) = Wf1 (u) [Wh1 (v) + Wh2 (v) ] + Wf2 (u) [Wh1 (v) - Wh2 (v) ] = (-1)0 Wf3 (u) [Wh3 (v) + Wh4 (v) ] + Wf4 (u) [Wh3 (v) - Wh4 (v) ]]. Therefore, g is (t + k + 2)-resilient.

Theorem 1: Let a function g ∈ Br+s+1 defined by (11). Then

The nonlinearity of g is:

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(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:

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(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:

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(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

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

Using relation (2)

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

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:

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

which implies that

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

Using (2) we deduce

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

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:

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

which, using (2)

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

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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity, the values of Wf1 (u), Wf2 (u), Wf3 (u) and Wf4 (u) and if for every Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity, the values of Wh1 (v), Wh2 (v), Wh3 (v) and Wh4 (v) are simultaneously null, or simultaneously non null, then g is a plateaued function with amplitude 2m+l+1.
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
Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
because f1, f2, f3, f4, are plateaued functions with the same amplitude 2m and h1, h2, h3, h4, are plateaued functions having the same amplitude 2l: then, g is a plateaued function with amplitude 2m+l+1.
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:
Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
then, we deduced that g is a plateaued function with amplitude 2m+l.

A new secondary construction of resilient functions: In this section, we present a new secondary construction of resilient functions on Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity 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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity n and let f and h be two n-variable t-resilient functions. Consider the functions g ∈ Bn+2 such that

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(16)

Where Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunityand y1, y2 ∈ F2. Note that the truth-table of g can be obtained by concatenating the truth-table of f and h. We have truth-tables:

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

The Walsh transforms of g is equal:

Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
(17)

Where Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunityand v1, v2 ∈ F2.

Truth-tables of Walsh transform g is:

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

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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunityof 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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunityof 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) = Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
is null for every Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity: The functions g is t-resilient. Moreover, if for every Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity of Hamming weight t+1, we have the values Wf (u), Wh (u) satisfy, respectively the relations Wh (u) – Wf (u) = 0, then for v1 ≠ v2 = 1, or 3Wf (u)+Wh (u) = 0, then for v1 = v2 = 0. We have Wg (u, v1, v2) = 0 it is deduced that the functions g is a t+1-resilient.

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
Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
using relation (2): This implies the inequality 2n+2 – 2Ng ≤ 3 x (2n – 2Nf) + 2n – 2Nh. We deduce that Ng ≥ 3Nf + Nh. Moreover if Nf = Nh = 2n¯1 – 2t+1, then from relation (18), we have Ng ≥ 2n¯1 – 2t+3 and if g is a t + 1-resilient, then from we have Ng ≤ 2n+1 – 2t+2: we deduce that the 2n+1 – 2t+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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunityis equal to
Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
Using relation (2), we have also 2n+2 – 2Ng = min (3 x (2n – 2Nf), 2n – 2Nh) and Ng are equals. Therefore Ng = 2n¯1 + min (3Nf, 2n + Nh). Thus, if f and h achieve a 2n¯1 – 2t+1 nonlinearity then from the relation (19), it is clearly that g achieves a maximum possible 2n¯1 – 3 x 2t+1 nonlinearity.
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
Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
Using relation (2), we have Ng ≥ 2n + Nf + Nh. Moreover if f and h achieve a 2n¯1 – 2t+1 nonlinearity, then from the relation (20), we deduce Ng≥2n+1–2t+2 and if g is a t + 1-resilient, then from we have Ng ≥2n+1–2t+2: we deduce then that the 2n+1–2t+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
Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
Using relation (2), we have 2n+2 – 2Ng = Min (2n – 2Nf, 2n – 2Nh) if f and h achieve a maximum possible 2n¯1 – 2t+1 nonlinearity and then from the relation (20) we have 2n+1 – 2t+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 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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity. Let g ∈ Bn+2 be function given by 16 then:

If for every all pair (v1, v2) ∈ F2 x F2 such that v1 = v2 = 0 and if for every Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunitythe values of Wf (u) and Wh (u) are simultaneously null, or simultaneously non null, then g is plateaued function with amplitude 2r+2 on Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity.
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 Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity.

Proof:

For every Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunityand for all pair (v1, v2) ∈ F2 x F2 we have Wg(u,v1 ,v2 ) =
Image for - Secondary Construction of Resilient Functions and Plateaued Functions: Study Their Algebraic Immunity
If v1 = v2 = 0 and if f and h are simultaneously null (resp. Simultaneously non null), we deduce that Wg (u, v1, v2) is equal to 3 x (±2r) + ±2r+2 because f and h are plateaued functions with amplitude 2r: g is a plateaued function with amplitude 2r+2.
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

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

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

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

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

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. 7-8, University of Rouen.

2:  Camion, P., C. Carlet, P. Charpin and N. Sendrier, 1992. On Correlation Immune Functions, Advances in Cryptology. Springer-Verlag, London.

3:  Carlet, C., 2001. On the coset weight divisibility and nonlinearity of resilient and correlation-immune functions. Proceedings of the Sequence and their Applications, (SETA'01), Springer-Verlag, London, pp: 131-144.

4:  Carlet, C. and P. Sarkar, 2002. Spectral domain analysis of correlation and resilient Boolean functions. Finite Fields Appli., 8: 120-130.

5:  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.

6:  Carlet, C., 2004. On the secondary constructions of resilient and bent functions coding, cryptography and combinatorics. Prog. Comput. Sci. Applied Logic, 23: 3-28.

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 4-9, 2005, Adelaide, SA., pp: 1101-1105.

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: 3105-3121.
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 3-7, 1996, Springer-Verlag, London, pp: 232-243.

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 4-8, 2002, Warsaw, pp: 346-359.

11:  Ding, C., G. Xiao and W. Shan, 1991. The stability theory of stream ciphers, N° 561, Lecture Note in Computer Sci., Vol. 561, Springer-Verlag, London.

12:  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.

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 15-19, 1999, Springer Verlag, London, pp: 198-215.

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

15:  Maitra, S. and P. Sarkar, 2002. Modifications of patterson- wideman functions for cryptographic applications. IEEE Trans. Inform. Theory, 48: 278-284.
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 2-6, 2004, Interlaken, pp: 474-491.

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 correlation-immune Boolean functions achieving upper bounds on nonlinearity. Elect. Notes Discrete Math., 6: 158-167.
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 14-18, 2000, Springer-Verlag, London, pp: 485-506.

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 14-18, 2000, Springer Verlag, London, pp: 515-532.

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 12-14, 1994, Springer-Verlag, London, pp: 181-199.

22:  Siegenthaler, T., 1984. Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Trans. Inform. Theory, 30: 776-780.

23:  Siegenthaler, T., 1985. Decrypting a class of stream ciphers using ciphertext only. IEEE Trans. Comput., 34: 81-85.

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 10-13, 2000, Springer-Verlag, London, pp: 19-30.

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 2-4, 2001, Springer-Verlag, London, pp: 66-77.

26:  Xiao, G.Z. and J.L. Massey, 1988. A spectral characterization of correlation-immune combining function. IEEE Trans. Theory Inform., 3: 569-571.

27:  Zheng, Y. and X.M. Zhang, 2000. Improving Upper Bound Cryptographic Properties, Lecture Note in Computer Science. Springer-Verlag, London, pp: 485-506.

©  2021 Science Alert. All Rights Reserved