COVERING RADIUS OF THE (N − 3)-RD ORDER
REED-MULLER CODE IN THE SET OF RESILIENT FUNCTIONS
Yuri BorissovInstitute of Mathematics and Informatics,Bulgarian Academy of Sciences,8 G.Bonchev, 1113 Sofia, [email protected] Braeken, Svetla NikovaDepartment Electrical Engineering, ESAT/COSIC,Katholieke Universiteit Leuven, Kasteelpark Arenberg 10,B-3001 Heverlee-Leuven, Belgiuman.braeken,[email protected]
In an important class of stream ciphers, called combination generators, the
key stream is produced by combining the outputs of several independent LinearFeedback Shift Register (LFSR) sequences with a nonlinear Boolean function. Siegenthaler [12] was the first to point out that the combining function shouldpossess certain properties in order to resist divide-and-conquer attacks.A Booleanfunction to be used in the combination generator (or more general also in streamciphers) should satisfy several properties. Balancedness – the Boolean functionhas to output zeros and ones with equal probabilities. High nonlinearity - theBoolean function has to be at sufficiently high distance from any affine func-tion. Correlation-immunity (of order t) - the output of the function should bestatistically independent of the combination of any t of its inputs. A balancedcorrelation-immune function is called resilient.
Besides the divide-and-conquer attacks, another important class of attacks
on combination generators are the algebraic attacks [4, 5]. The central idea in thealgebraic attacks is to use a lower degree approximation of the combining Booleanfunction and then to solve an over-defined system of nonlinear multivariate equa-tions of low degree by efficient methods such as XL or simple linearization [3]. Inorder to resist these attacks, the Boolean function should have not only a a highalgebraic degree but also a high distance to lower order degree functions. Thetrade-off between resiliency and algebraic degree is well-known. To achieve the
desired trade-off designers typically fix one or two parameters and try to optimizethe others.
In this paper, we investigate the generalization of the trade-off between re-
siliency and algebraic degree. In particular, we study the relation between re-siliency and distance to lower order degree functions. In order to define a the-oretic model for combining these properties, Kurosawa et al. [6] have intro-duced a new covering radius ˆ(t, r, n), which measures the maximum distancebetween t-resilient functions and r-th degree functions or the r-th order Reed-Muller code RM (r, n). That is ˆ(t, r, n) = max d(f (x), RM(r, n)), where themaximum is taken over the set Rt,n of t-resilient Boolean functions of n vari-ables. Note that as the covering radius of Reed-Muller codes is defined by
(r, n) = max d(f, RM(r, n)) where the maximum is taken over all Boolean func-
tions f , it holds that 0 ≤ ˆ(t, r, n) ≤ (r, n). Kurosawa et al. also provide a tablewith certain lower and upper bounds for ˆ(t, r, n). In [1] some exact values andnew bounds for the covering radius of the second order Reed-Muller codes in theset of resilient functions were found.
In this paper we find the exact value of the covering radius of RM (n − 3, n)
in the set of 1-resilient Boolean functions of n variables, when n/2 = 1mod 2. We also improve the lower bounds for covering radius of the Reed-Muller codesRM(r, n) in the set of t-resilient functions, where r/2 = 0mod 2, t ≤ n − r − 2and n ≥ r + 3. We start with some background on Boolean functions.
Any Boolean function f (x) on Fn can be uniquely expressed in the algebraic
hf (a1, . . . , an)xa1 · · · xan,
(a1,.,an)∈Fn
with hf a function on Fn, defined by hf (x) for any a ∈ Fn, where
x ≤ a means that xi ≤ ai for all i ∈ {1, . . . , n}. The algebraic degree of f, denotedby deg(f ) or shortly d, is defined as the number of variables in the highest termxa1 · · · xan in the ANF of f for which hf (a1, . . . , an) = 0. The suport of f , denoted
by sup(f ), is the set of all vectors x for which f (x) = 0. The Walsh transform of
f (x) is a real-valued function over Fn that is defined as
(−1)f(x)+x·ω,
where x · w denotes the dot product of the vectors x and w, i.e., x · w = x1w1 +· · · + xnwn.
Definition 1 A function f (x) is called t-th order correlation-immune if its Walshtransform satisfies Wf (ω) = 0, for 1 ≤ wt(ω) ≤ t, where wt(x) denotes theHamming weight of x. Balanced t-th order correlation-immune functions arecalled t-resilient functions, i.e. Wf (ω) = 0, for 0 ≤ wt(ω) ≤ t.
By the well-known Siegenthaler’s inequality [11] the maximal possible alge-
braic degree of t-resilient function f of n variables is equal to n − t − 1 whent < n − 1. The problem for constructing resilient functions (in particular suchof maximal possible degree) attracted the attention of many authors in the past. Among other works we mention [11], [2] and [10]. The next theorem shows howwe can easily construct (t + 1)-resilient function on Fn+1 from t-resilient function
Lemma 2 [2] Let xn+1 be a linear variable, i.e., f(x1, . . . , xn, xn+1) = g(x1, . . . , xn)+ xn+1, where g(x1, . . . , xn) is t-resilient. Then f(x1, . . . , xn, xn+1) is (t + 1)-resilient.
We also make use of the following theorem:
Theorem 3 [7] The covering radius of RM (n − 3, n) is equal to n + 2 if n iseven. If n is odd, the covering radius is equal to n + 1.
To prove the theorem, McLoughlin constructed a coset for which the minimalweight is equal to n + 2 when n is even, and n + 1 when n is odd. This cosetcontains σn−2, the symmetric polynomial consisting of all terms of degree n − 2.
THE COVERING RADIUS OF (N − 3)-RD REED-MULLER CODES IN THESET OF 1-RESILIENT BOOLEAN FUNCTIONS
In order to prove the main theorem of this paper we will need the following
Lemma 4 Let σi(x) be the symmetric polynomial of n variables containing allterms of degree i (σ0(x) = 1) and S(x) =
0, n − 1, n when n is even;v ∈ sup(S) if and only if wt(v) =
Proof. Let v ∈ Fn be a vector of weight w. It is easy to see that the number of
terms in σi(v) equal to 1 is w (as usual w = 0, when w < i). Therefore the
number of terms in S(v) that are equal to 1 is N(w) =
N(w) mod 2. There are four cases to be considered:
1. If w = 0, then S(0) = 1;
2. If 0 < w < n − 1, then N(w) = 2w and thus S(v) = N(w) mod 2 = 0;
3. If w = n − 1, we have N(n − 1) =
= 2n−1 − 1 and therefore
4. If w = n, we have N(n) =
n−2 n = 2n − (n + 1). Therefore
Lemma 5 Let S(x) be the symmetric Boolean function of n variables, defined inLemma 4, where n is equal to 4k + 2 or equal to 4k + 3. Let v be an arbitraryvector of weight 2k + 1 or of weight 2k + 2. Then the Walsh transform valueWS(v) = 0.Proof. Let us consider the following two linear functions: L1(x) =
i. Arranging the set sup(S) in decreasing lexicographic order,
it is easy to see that Lj = 0, j = 1, 2 for the half of the vectors from sup(S). Since the linear functions are balanced the same is true for the complement set ofsup(S), in which S takes value 0. Therefore L1 and L2 differ from S in 2n−1 pointsi.e. d(Lj, S) = 2n−1, j = 1, 2. By using the relation Wf (ω) = 2n − 2 d( ω, x , f)we get WS(v) = 0 where v is either the vector having only ones in the first 2k + 1or in the first 2k + 2 coordinates. Since S(x) is a symmetric function this holdsfor any vector of weight 2k + 1 or 2k + 2.
Let T be a subset of Fn. The rank of T , denoted by rank(T ), is defined as
the maximal number of linearly independent elements from T .
Lemma 6 Let n be equal to 4k + 2 or equal to 4k + 3 and Z = {v ∈ Fn : wt(v) =
2k + 1 or 2k + 2}. Denote by v1 the vector (1, 1, 1, .1, 0, 0, 0, .0) of weight 2k + 1. Then the set Z + v1 has rank n.Proof. Note that the following vectors of weight 2
(1, 0, 0, ., 0, 1, 0, .0), (0, 1, 0, ., 0, 1, 0.0), . . . , (0, 0, 0, ., 1, 1, 0.0),
where the second “1” is in the (2k + 2)-nd position, belong to Z + v1. The sameis valid for the vectors having only one “1” in positions 2k + 2 till n. Obviously,these are n linearly independent vectors and the proof is complete.
Theorem 7 The covering radius of RM(n-3,n) in the set of 1-resilient Booleanfunctions of n variables is equal to:Proof. By the result of McLoughlin [7] (see Theorem 3), the Boolean function
S(x) defined in Lemma 4, belongs to the coset of RM (n − 3, n) with a maximalpossible minimal weight. By Lemma 5 and Lemma 6 and using the procedure for“change the basis” described by Maitra and Pasalic [9] the function S(x) is affinereducible to 1-resilient function.
Finally, let us consider the case n = 4. It is easy to see that σ2 is affine
equivalent to some function in the coset of RM(1, 4) containing the function f =x1x2 + x3x4. However f is a bent function and therefore the coset σ2 + RM(1, 4)contains no balanced functions. By Dickson [8] theorem the remaining two typesof cosets (which are interesting when consider 1−resilient functions of 4 variables),are RM(1,4) itself and these equivalent to x1x2 + RM(1, 4). In fact the functiong = x1x2 + x3 + x4 is 1-resilient and the minimal weight of its coset is 4. Hencethe covering radius of interest is 4 (see also numerical results in [6]).
DERIVING NEW LOWER BOUNDS ON THE COVERING RADIUS OF REED-MULLER CODE IN THE SET OF RESILIENT FUNCTIONS
By induction, using Theorem 3 and Theorem 7, we can also generalize the
lower bounds for RM (r, n) in the set of t-resilient functions where r/2 =0 mod 2, t ≤ n − r − 2 and n ≥ r + 3.
Theorem 8 The covering radius of the Reed-Muller code RM (r, n) in the setRt,n for r/2 = 0 mod 2, t ≤ n − r − 2 and n ≥ r + 3 is bounded from below by2n−3.
In particular, for r = 3 and r = 4, this leads to the following lower bound:
Corollary 9 The covering radius of the Reed-Muller code RM (3, n) in the setRt,n for t ≤ n − 5 is bounded from below by 2n−3, when n ≥ 6. The coveringradius of the Reed-Muller code RM(4, n) in the set Rt,n for t ≤ n − 6 is boundedfrom below by 2n−3, when n ≥ 7, i.e.
ˆ(t, 3, n) ≥ 2n−3
ˆ(t, 4, n) ≥ 2n−3
for t ≤ n − 6, n ≥ 7.
In this paper, we continued the study of the covering radius in the set of
resilient functions, which has been defined by Kurosawa et al. [6]. This newconcept is meaningful to cryptography especially in the context of the new classof algebraic attacks on stream ciphers proposed by Courtois and Meier at Euro-crypt 2003 [4] and Courtois at Crypto 2003 [5]. In order to resist such attacksthe combining Boolean function should be at high distance from lower degreefunctions.
Using a result from coding theory on the covering radius of (n − 3)-rd Reed-
Muller codes, we establish exact values of the the covering radius of RM (n − 3, n)in the set of 1-resilient Boolean functions of n variables, when n/2 = 1mod 2. We also improve the lower bounds for covering radius of the Reed-Muller codesRM(r, n) in the set of t-resilient functions, where r/2 = 0mod 2, t ≤ n − r − 2and n ≥ r + 3.
In the table below we present the improved numerical values of the covering
radius for resilient functions. The entry α − β means that α ≤ ˆ(t, r, n) ≤ β.
Table 1: Numerical data of the bounds on ˆ(t, r, n)
[1] Y. Borissov, A. Braeken, S. Nikova, B. Preneel, On the Covering Radius of
Second Order Binary Reed-Muller Code in the Set of Resilient Boolean Func-tions, IMA International Conference on Cryptography and Coding, Springer-Verlag LNCS 2898, 2003, pp. 82-92.
[2] P. Camion, C. Carlet, P. Charpin, N. Sendrier, On Correlation Immune
Functions,CRYPTO’91, LNCS 576, Springer-Verlag 1991, pp. 87-100.
[3] N. Courtois, A. Klimov, J. Patarin, A. Shamir, Efficient Algorithms for
Solving Overdefined Systems of Multivariate Polynomial Equations, Euro-crypt’00, LNCS 1807, Springer-Verlag, 2000, pp. 392-407.
[4] N. Courtois, W. Meier, Algebraic Attacks on Stream Ciphers with Linear
Feedback, Eurocrypt’03, LNCS 2656, Springer-Verlag 2003, pp. 345-359.
[5] N. Courtois, Fast Algebraic Attacks on Stream Ciphers with Linear Feedback
Crypto’03, LNCS 2729, Springer-Verlag 2003, pp. 176-194.
[6] K. Kurosawa, T. Iwata, T. Yoshiwara, New Covering Radius of Reed-Muller
Codes for t-Resilient Functions, SAC’01, LNCS 2259, Springer-Verlag 2001,pp. 75-86.
[7] A. McLoughlin, The Covering Radius of the (m − 3)−rd Order Reed-Muller
Codes and a Lower Bound on the (m − 4)−th Order Reed-Muller Codes,SIAM J. Appl. Mathematics, vol. 37, No. 2, October 1979, pp. 419-422.
[8] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes,
North-Holland Publishing Company 1977.
[9] S. Maitra, E. Pasalic, Further Constructions of Resilient Boolean Functions
with Very High Nonlinearity, IEEE Transactions on Information Theory,vol. 48, No.7, July 2002, pp. 1825-1834.
[10] J. Seberry, J. Zhang, Y. Zheng, On Constructions and Nonlinearity of Cor-
relation Immune Functions, Eurocrypt’93, LNCS 765, Springer-Verlag 1994,pp. 181-199.
[11] T. Siegenthaler, Correlation-Immunity of Non-linear Combining Functions
for Cryptographic Applications, IEEE IT, vol. 30, No. 5, 1984, pp. 776-780.
[12] T. Siegenthaler, Decrypting a Class of Stream Ciphers Using Ciphertext
Only, IEEE Trans. Comp., vol 34, No. 1, 1985, pp. 81-85.
[13] Y. Tarannikov, On Resilient Functions with Maximun Possible Nonlinearity,
Indocrypt 2000, LNCS 1977, pp. 19-30.

A Randomized, Placebo-Controlled Trial of Citalopram for the Prevention of Major Depression During Treatment for Head and Neck Cancer William M. Lydiatt, MD; David Denman, MD; Dennis P. McNeilly, PsyD;Susan E. Puumula, MS; William J. Burke, MD Objective: To determine whether prophylactic treat- Results: The numbers of subjects who met predefined ment with the antidepressant citalopram h

Is There No Place on Earth for Me? Is There No Place on Earth for Me?, Susan Sheehan’s chronicle of a schizophrenic’s experience with the mental health establishment, is dense, informative, and thoroughly depressing. Those hardy enough to wade through the book are unlikely to find it an enjoyable read, but will come away impressed by the meticulous detail and artful structure apparent i