Eprint.iacr.org

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 h f (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 h f (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.

Source: https://eprint.iacr.org/2004/202.pdf