Leonid A Bassalygo

Victor A Zinoviev

On divisibility of exponential sums of polynomials of special type over fields of characteristic 2 ⋆

Keywords: exponential sum, Kloosterman sum, divisibility by power of two, zero of Kloosterman sum

We study divisibility by eight of exponential sums of several classes of functions over finite fields of characteristic two. For the binary classical Kloosterman sums K(a) over such fields we give a simple recurrent algorithm for finding the largest k, such that 2 k divides the Kloosterman sum K(a). This gives a simple description of zeros of such Kloosterman sums.

1. Introduction. Let F = F 2 m be the field of characteristic 2 of order 2 m , where m ≥ 3 is an integer. By F 2 denote the field, consisting of two elements. Set e(x) = (-1)

Tr(x) , x ∈ F,
where Tr(x) is the trace function from F into F 2 . For an arbitrary polynomial f (x) over F define its exponential sum S(f ),

S(f ) = x∈F e(f (x)).
Recall that under x -i we understand x 2 m -1-i , avoiding by this way a division into 0. The sum K(a) = x∈F e(x + a/x), a ∈ F * , is called the Kloosterman sum. Given a polynomial f (x) over F it is a hard mathematical problem to write out the value of its exponential sum S(f ) or the module |S(f )|. This problem is interesting from several points of view, for example, for the theory of errorcorrecting codes, for sequences, for solving of equations over finite fields, for cryptography and etc. In some cases the value S(f ) is known (see [START_REF] Bassalygo | Polynomials of special form over finite fields with given values of exponential sum[END_REF], [START_REF] Carlitz | Explicit evaluation of certain exponential sums[END_REF], [START_REF] Lidl | Finite Fields[END_REF] and references there). From this point of view, the divisibility of S(f ) is an interesting important open problem. Recently, the divisibility of K(a) has been considered in several papers. In particular, the divisibility of K(a) modulo 24 has been solved in [START_REF] Charpin | On divisibility properties of classical binary Kloosterman sums[END_REF], and the divisibility by 16 has been solved in [START_REF] Lisonek | On zeros of Kloosterman sums, Designs, Codes and Cryptography[END_REF].

In the present paper we use an elementary combinatorial approach to study divisibility by eight of exponential sums of polynomials of special type (such as a(x d + x -d ), ax d + bx -1 , a(x + x -1 ) d , and etc.). This is considered in the first three sections. In the last section we consider the divisibility of Kloosterman sums K(a) into the maximal power of two, which results in a simple algorithm of finding of zeros of Kloosterman sums. Kloosterman zeros play a significant role in construction of highly nonlinear functions that are used in cryptography, in particular, for construction of bent functions (see [START_REF] Charpin | Hyperbent functions, Kloosterman sums, and Dickson polynomials[END_REF], [START_REF] Dillon | Elementary Hadamard difference sets[END_REF]) and hyperbent functions (see [START_REF] Charpin | Hyperbent functions, Kloosterman sums, and Dickson polynomials[END_REF]).

2. Polynomials of type a(x d + x -d ). We start by studying the divisibility by 8 of exponential sums of polynomials f (x) of the type

f (x) = a(x d + x -d ), a ∈ F * ,
where d is any odd integer, 1 ≤ d ≤ 2 m -3. All our proofs of divisibility by eight are based on the following quite evident observation. Let β be a primitive element of F. For a given a ∈ F * and an odd integer d, 1 ≤ d ≤ 2 m -3, define a binary vector of length 2 m :

T (a x d ) = (Tr (0), Tr (a), Tr (a β d ), Tr (a β 2d ), ..., Tr (a β (2 m -2)d )).
In the similar way define the vector T (a x -d ) of the same length. Denote

T 1 (a x d ) = (Tr (a β d ), Tr (a β 2d ), ..., Tr (a β (2 m-1 -1)d ))
and

T 2 (a x d ) = (Tr (a β 2 m-1 d ), Tr (a β (2 m-1 +1)d ), ..., Tr (a β (2 m -2)d )).
Similarly define also the vectors T 1 (a x -d ) and T 2 (a x -d ). Note that the vector

(T 1 (a x -d ), T 2 (a x -d )) of length 2 m -2 is an inversion of the vector (T 1 (a x d ), T 2 (a x d )). Since x∈F Tr (a x d ) = Tr 2 m -2 i=0 a β i d = Tr a β d(2 m -1) -1 β -1 = 0,
the weight of the vector (T 1 (a x d ), T 2 (a x d )) is even, if Tr(a) = 0. The same property is valid for the vector (T 1 (a x -d ), T 2 (a x -d )). But if Tr(a) = 1, then the corresponding weights are odd. Therefore, according to Proposition 1 we obtain that

d (T (a x d ), T (a x -d )) ≡ 0 (mod 4), if Tr (a) = 0, 2 (mod 4), if Tr (a) = 1. Since S(a(x d + x -d )) = 2 m -2 d (T (a x d ), T (a x -d )),
the following result holds.

Statement 1 . Let a ∈ F * , and d be any odd integer,

1 ≤ d ≤ 2 m -3. Then S(a (x d + x -d )) ≡ 0 (mod 8), if Tr(a) = 0, 4 (mod 8), if Tr(a) = 1.
The proof given above is quite elementary. Remark, that this result was known for d = 1 and, therefore, for any d which is relatively prime to 2 m -1 (see [START_REF] Helleseth | On Z4-Linear Goethals Codes and Kloosterman Sums, Designs[END_REF], where two proofs of this result are given: the first one based on finding of the number of solutions of some system of equations over F, and the second one, suggested by P. Charpin, based on Melas codes).

It is easy to see that the sum S(a(x d + x -d )) depends on the value of the greatest common divisor h = (d, 2 m -1) of numbers d and 2 m -1. In particular, h divides S(a(x d + x -d )) -1. Indeed, denoting 2 m -1 = hu, we obtain

S(a(x d + x -d )) = 1 + 2 m -2 i=0 e(a (β i d + β -i d )) = 1 + 2 m -2 i=0 e(a β i d ) e(a β -i d ) = 1 + u-1 j=0 h-1 s=0 e(a (β (j+s u) d )e(a β -(j+s u) d ) = 1 + u-1 j=0 e(a β j d ) e(a β -j d ) h-1 s=0 e(a β s u d )e(a β -s u d ) = 1 + h u-1 j=0 e(a β j d ) e(a β -j d ) = 1 + h u-1 j=0 e(a (β j d + β -j d )).
From the last expression and Statement 1 we have the following Statement 2 . Let d be any odd integer, 1 ≤ d ≤ 2 m -3, and h = (d, 2 m -1). For any elements a 1 , a 2 ∈ F * the following congruence is valid:

S(a 1 (x d + x -d ))-S(a 2 (x d + x -d )) ≡ 0 (mod 4
i ≤ 2 m -3, i = 1, . . . , t. Then S t i=1 a i (x di + x -di ) ≡ 0 (mod 8), if Tr ( t i=1 a i ) = 0, 4 (mod 8), if Tr ( t i=1 a i ) = 1.
3. Polynomials of type a(x + x -1 ) d . Now consider polynomials f (x) = a(x + x -1 ) d , where

d = ℓ j=0 2 dj is any odd number, 3 ≤ d ≤ 2 m -3, m > d ℓ > d ℓ-1 > . . . > d 0 = 0 and ℓ ≥ 1. Clearly f (x) = a x + x -1 P ℓ j=0 2 d j = a ℓ j=0 x 2 d j + x -2 d j = k a (x k + x -k ),
where summing is taken over all k of the type

k = 2 d ℓ ± 2 d ℓ-1 ± . . . ± 1
(i.e. the value k takes 2 ℓ different values). Since T r( k a) = 0 (indeed, the sum consists of even number of monoms), then according to Statement 3 (taking into account, that a i = a for all i = 1, . . . , 2 ℓ ) we obtain the following result. From Statement 3 also follows more general result.

Statement 5 . Let a 1 , . . . , a t ∈ F * , d 1 , . . . , d t be any odd numbers, 3

≤ d i ≤ 2 m -3. Then S   t j=1 a j (x + x -1 ) dj   ≡ 0 (mod 8).
Remark 1 . Clearly Statement 5 is still satisfied, if we change x + x -1 by x r + x -r , where r is any integer, 3 ≤ r ≤ 2 m -3.

Polynomials of type

a x d + b x -1 . Consider now polynomials f (x) = a x d + b x -1
, where a, b ∈ F, a = 0, and d is any odd number, 1 ≤ d ≤ 2 m -3. First prove the following statement.

Proposition 2 . Let c ∈ F * . Then S(c x d + x -1 ) + S(c x d ) = S(c (x + x -1 ) d ).
Proof. The following chain of equalities takes place:

S(c x d + x -1 ) + S(c x d ) = Tr(x -1 )=0 e(cx d + x -1 ) + Tr(x -1 )=1 e(cx d + x -1 ) + Tr(x -1 )=0 e(cx d ) + Tr(x -1 )=1 e(cx d ) = Tr(x -1 )=0 e(cx d + x -1 ) + Tr(x -1 )=0 e(cx d ) = 2 × x∈F: Tr(x -1 )=0
e(cx d ).

Since the equation

y + 1 y = x, x ∈ F (1)
has two distinct zeros y 1 , y 2 in the field F, if and only if Tr(x -1 ) = 0 (see [START_REF] Lidl | Finite Fields[END_REF]) and the number of the elements x ∈ F, such that Tr(x -1 ) = 0, is equal to 2 m-1 , then the solutions y 1 , y 2 of the equation ( 1), for all such x, run over the all field F. Therefore, Theorem B [START_REF] Lisonek | On zeros of Kloosterman sums, Designs, Codes and Cryptography[END_REF]). Let a ∈ F * , and let 0 ≤ k ≤ m. Then 2 k |K(a) if and only if there exists a point of order 2 k on E(a), where the curve E(a) is defined by [START_REF] Charpin | On cosets of weight 4 of binary primitive BCH codes of length 2 m (m even) with minimum distance 8 and exponential sums[END_REF].

For a given element a ∈ F * , define now the sequence x 1 , x 2 , . . . , x k of elements of the field F by the following recurrent expression:

x 1 = 0, x 2 i+1 + √ x i x i+1 + a = 0, i = 1, . . . , k -1. (4)
The following one of the main results follows from Lemma A and Theorem B.

Theorem 1 . Let a be any element of F * and let a sequence of elements x 1 , x 2 , . . . , x k be constructed in accordance with recurrent relation [START_REF] Charpin | On divisibility properties of classical binary Kloosterman sums[END_REF]. Let k be the smallest natural number, such that Tr(x k ) = 1. Then the Kloosterman sum K(a) is divisible by 2 k and is not divisible by 2 k+1 .

It is interesting to find a direct proof of Theorem 1, which does not use a transition to the number of rational points of the elliptic curve E(a).

Corollary 3 [START_REF] Helleseth | On Z4-Linear Goethals Codes and Kloosterman Sums, Designs[END_REF]. Since x 2 = √ a, then K(a) is divisible by 4, but not divisible by 8, if T r(a) = 1.

Corollary 4 [START_REF] Helleseth | On Z4-Linear Goethals Codes and Kloosterman Sums, Designs[END_REF], [START_REF] Lisonek | On zeros of Kloosterman sums, Designs, Codes and Cryptography[END_REF]. Let T r(a) = 0. Then a can be presented as a = z 8 +z 16 . In this case x 3 = z 6 + z 8 . If T r(z) = T r(z 3 ), then K(a) is divisible by 8, but not divisible by 16.

Corollary 5 [START_REF] Lisonek | On zeros of Kloosterman sums, Designs, Codes and Cryptography[END_REF]. Under conditions of the Corollary 4 above, if T r(z) = T r(z 3 ), then K(a) is divisible by 16. Recall (see [START_REF] Charpin | Hyperbent functions, Kloosterman sums, and Dickson polynomials[END_REF] and references there) that the function f a,r (x), f a,r (x) = Tr a x r(2 m/2 -1) , a ∈ F * , for even m and natural r, such that r and 2 m/2 + 1 are mutually prime, is bent, if and only if K(a) = 0, and the function f a (x) f a (x) = Tr a x 2 m -1 , a ∈ F * , is hyperbent, if and only if K(a) = 0.

Theorem 1 implies the following simple necessary and sufficient condition for an element a to be a zero of the Kloosterman sum K(a), i.e. in order to have K(a) = 0. Theorem 2 . Let a be any element of F * and let a sequence u 1 , u 2 , . . . , u m of elements from F be defined in accordance with the following recurrent relation:

u i+1 = u 2 i + a 2 u 2 i ,

Proposition 1 .

 1 Let b = (b 1 , . . . , b k , b k+1 , . . . , b 2k ) be a binary sequence of even length 2k, and let b inv = (b 2k , . . . , b k+1 , b k , . . . , b 1 ) be the inverse sequence. Then the Hamming distance d (b, b inv ) ≡ 0 (mod 4), if wt(b) even, 2 (mod 4), if wt(b) odd, where wt(b) is the Hamming weight of b (i.e. the number of ones in the sequence b).

Statement 4 .

 4 Let a ∈ F * and d be any odd number, 3 ≤ d ≤ 2 m -3. Then S a (x + x -1 ) d ≡ 0 (mod 8).

2 ×Statement 6 .

 26 x∈F: Tr(x -1 )=0 e ( c x d ) = y∈F e (c (y + 1 y ) d ) = S (c (x + x -1 ) d ). △ From Proposition 2 and Statement 4 the following statement follows. Let a, b ∈ F * and d be any odd integer, 3 ≤ d ≤ 2 m -3. Then S (a x d + b x -1 ) ≡ 0 (mod 8), if and only if S (a x d ) ≡ 0 (mod 8).

  h), if Tr(a 1 ) = Tr(a 2 ), 0 (mod 8 h), if Tr(a 1 ) = Tr(a 2 ), .From the proof of Statement 1 also follows clearly the following more general Statement 3 . Let a 1 , . . . , a t ∈ F * and d 1 , . . . , d t be any odd numbers, 1 ≤ d

⋆ Supported by the Russian Fundamental Research Foundation, project No. 09 -01 -00536.

Corollary 2 . Since S (a x 3 ) ≡ 0 (mod 8) for even m ≥ 6 (see [START_REF] Carlitz | Explicit evaluation of certain exponential sums[END_REF]), then

This result was known (see [START_REF] Charpin | On cosets of weight 4 of binary primitive BCH codes of length 2 m (m even) with minimum distance 8 and exponential sums[END_REF]).

5. Kloosterman sums. Now consider Kloosterman sums K(a). Here we study the divisibility of such sums by the maximal possible number of the type 2 k (i.e. 2 k divides K(a), but 2 k+1 does not divide K(a)).

We are going to formulate a simple recurrent algorithm for finding the largest k, such that 2 k divides the Kloosterman sum K(a). Before it, recall Lemma 7.4 in [START_REF] Menezes | Elliptic Curve Public Key Cryptosystems[END_REF].

Lemma A [START_REF] Menezes | Elliptic Curve Public Key Cryptosystems[END_REF]. Let polynomials g i = g i (x) over F be defined by the following recurrent construction:

Then the all zeros of the polynomial g k-1 gives the x-th coordinates of the points of order 2 k of the elliptic curve E(a) over F, defined by the following equation:

Now recall the following result due to Lisonek P. (see reference in [START_REF] Lisonek | On zeros of Kloosterman sums, Designs, Codes and Cryptography[END_REF]), which we formulate only for p = 2.

where u 1 ∈ F * is any element of F * , such that Tr(u 1 ) = 1 and Tr(u 1 + a u 1 ) = 0.

Then K(a) = 0, if and only if u m = 0, and the all m -1 elements u 1 , . . . u m-1 are nonzero. Furthermore, if the first zero element in the sequence u 1 , u 2 , . . . , u m appears on the kth place, where k < m, then k is the largest integer, such that 2 k divides K(a).


Faruk Göloglu

Gary Mcguire

Richard Moloney

Some Results on Kloosterman Sums and their Minimal Polynomials

This paper introduces two new results on Kloosterman sums and their minimal polynomials. We characterise ternary Kloosterman sums modulo 27. We also prove a congruence concerning the minimal polynomial over Q of a Kloosterman sum. This paper also serves as a survey of our recent results on binary Kloosterman sums modulo 16, 32, 64 and 128 with Petr Lisoněk.

Introduction

Throughout the paper let p be a prime, n ≥ 1 an integer, q = p n and ζ a primitive p th root of unity. We let F q denote the finite field with q elements, and let Tr denote the absolute trace function Tr : F q → F p , Tr(a) = a + a p + a p 2 + • • • + a p n-1 .

The Kloosterman sum of a ∈ F q is defined to be

K q (a) = x∈Fq ζ Tr(x -1 +ax)
where we interpret 0 -1 as 0. We remark that some authors do not include 0 in the definition of Kloosterman sum.

Kloosterman sums are Walsh transform values of the inverse function over F q , therefore have a cryptographic significance as the inverse function is used in AES (the Advanced Encryption Standard) and Walsh transform values of a function is related to linear cryptanalysis. Exponential sums and in particular Kloosterman sums have coding theoretical and combinatorial significance. Kloosterman and Melas codes, bent functions are the best known examples (see [START_REF] Hurt | Exponential sums and coding theory: a review[END_REF] for an excellent survey).

Kloosterman sums are real numbers. Binary and ternary Kloosterman sums are always integers. If p > 3 there are Kloosterman sums that are not integers. An interesting problem is to find the 'smallest' ring to which all the Kloosterman sums over F q belong. The Lachaud-Wolfmann result [START_REF] Lachaud | The weights of the orthogonals of the extended quadratic binary Goppa codes[END_REF] does that for the binary case and states that Kloosterman sums satisfy

-2 n/2+1 ≤ K 2 n (a) ≤ 2 n/2+1 ,
and take every value which is congruent to 0 modulo 4 in that range. Hence, all binary Kloosterman sums are precisely the integers in 4Z within the Weil bound. For the ternary case, Kloosterman sums satisfy (see Katz and Livné [11])

-2 √ 3 n < K 3 n (a) < 2 √ 3 n
and take every value which is congruent to 0 modulo 3 in that range. For p > 3 a similar congruence result is unknown.

A related question is the existence of a Kloosterman zero, i.e., an element a ∈ F * q (non-zero elements of F q ) such that K q (a) = 0. The results of Lachaud and Wolfmann [START_REF] Lachaud | The weights of the orthogonals of the extended quadratic binary Goppa codes[END_REF] (resp. Katz and Livne [START_REF] Katz | Sommes de Kloosterman et courbes elliptiques universelles caractéristiques 2 et 3[END_REF]) guarantees the existence of binary (resp. ternary) Kloosterman zeroes. Kononen, Rinta-aho and Väänänen have proved recently [START_REF] Kononen | On integer values of Kloosterman sums[END_REF] that if p > 3 then no Kloosterman zero exists. Kloosterman zeroes for the binary and ternary case are linked to existence of bent functions [START_REF] Dillon | Elementary Hadamard Difference Sets[END_REF][START_REF] Helleseth | Monomial and quadratic bent functions over the finite fields of odd characteristic[END_REF].

Characterising Kloosterman zeroes seems to be difficult. Lisoněk and Moisio showed that other than p = 2, n = 4 and a = 1 if a belongs to a proper subfield of F q then K q (a) cannot be zero. Another way of approaching this problem is to give congruences of Kloosterman sum modulo some integers. This was done for binary Kloosterman sums for moduli 3, 8, 24 in [START_REF] Van | Kloosterman sums and the ptorsion of certain Jacobians[END_REF][START_REF] Helleseth | On Z4-linear Goethals codes and Kloosterman sums[END_REF][START_REF] Charpin | The divisibility modulo 24 of Kloosterman sums on GF (2 m ), m odd[END_REF][START_REF] Garaschuk | On binary Kloosterman sums divisible by 3. Designs[END_REF][START_REF] Moisio | The divisibility modulo 24 of Kloosterman sums on GF (2 m ), m even[END_REF]. In the next section we survey our recent results for moduli 16, 32, 64, 128 with Petr Lisoněk.

For the ternary case, Lisoněk proved a result for divisibility by 9 in [START_REF] Lisoněk | On the connection between Kloosterman sums and elliptic curves[END_REF]. We have recently given a complete modulo 9 characterisation [START_REF] Göloglu | Ternary Kloosterman sums modulo 18 using Stickelberger's theorem[END_REF] (we should note here this result was implicit in [START_REF] Van | Kloosterman sums and the ptorsion of certain Jacobians[END_REF]). In this paper we give a modulo 27 characterisation. For p > 3, since Kloosterman sums are not necessarily integers, we resort to the analysis of the minimal polynomial of Kloosterman sums over Q. What we prove in Section 3 can be seen as a generalisation of our ternary result of [START_REF] Göloglu | Ternary Kloosterman sums modulo 18 using Stickelberger's theorem[END_REF] to arbitrary p.

In Section 2 we give a brief survey on binary Kloosterman sums modulo some powers of 2. The characterisations use help from some functions from finite fields. Proofs of the results of Section 2 can be found in [START_REF] Göloglu | Binary Kloosterman sums modulo 128 and coefficients of the characteristic polynomial[END_REF]. In Section 3 we give our first new and unpublished result on the minimal polynomial of p-ary Kloosterman sums. Our second new result is in Section 4. We give a characterisation of ternary Kloosterman sums modulo 27 using trace-like functions on finite fields. Our proof methods use algebraic number theory: Stickelberger's theorem and Gross-Koblitz formula and Fourier analysis (see [START_REF] Göloglu | Some congruences of Kloosterman sums and their minimal polynomials[END_REF]).

Binary Kloosterman sums

In this section let p = 2 and q = 2 n . Furthermore let a ∈ F q , and consider the characteristic polynomial of a;

n-1 i=0 (x -a 2 i ) = x n + ē1 x n-1 + ē2 x n-2 + • • • + ēn .
Each of the ēi is in F 2 , ē1 is the trace of a and ē2 is sometimes called the subtrace (or quadratic trace). For i > n, set ēi = 0.

Let e i ∈ {0, 1} denote ēi viewed as an integer.

Note that the only reason we restrict the integers e i to the set {0, 1} is so that we can identify e 2 i with e i , allowing us to eliminate exponents and reduce the length of certain expressions in e i .

For any positive integer j, let wt 2 (j) denote the binary weight of j, i.e., wt 2 (j) = i j i where i j i 2 i is the binary expansion of j. With this notation, we can write ēi for 0 ≤ i ≤ n as ēi = wt2(j)=i a j .

Survey of results on Kloosterman sums modulo powers of 2

Using this notation we rephrase the known results.

The first result is usually attributed to Helleseth and Zinoviev [START_REF] Helleseth | On Z4-linear Goethals codes and Kloosterman sums[END_REF], but it also appears in an earlier paper by van der Geer and van der Vlugt [START_REF] Van | Kloosterman sums and the ptorsion of certain Jacobians[END_REF].

Theorem 1 Let q ≥ 8. For a ∈ F q , K q (a) ≡ 4e 1 (mod 8).

This gives a condition for divisibility by 8.

Corollary 2 Let q ≥ 8 and let a ∈ F q . Then K q (a) ≡ 0 (mod 8) if and only if e 1 = 0.

The following theorem is in [START_REF] Göloglu | Binary Kloosterman sums using Stickelberger's theorem and the Gross-Koblitz formula[END_REF].

Theorem 3 Let q ≥ 16. For a ∈ F q , K q (a) ≡ 12e 1 + 8e 2 (mod 16).

Again, this gives a divisibility condition.

Corollary 4 [START_REF] Göloglu | Binary Kloosterman sums using Stickelberger's theorem and the Gross-Koblitz formula[END_REF] Let q ≥ 16 and let a ∈ F q . Then K q (a) ≡ 0 (mod 16) if and only if e 1 = 0 and e 2 = 0.

Note that this mod 16 divisibility criterion was stated earlier in a different but equivalent form in [START_REF] Lisoněk | On the connection between Kloosterman sums and elliptic curves[END_REF].

Now we give a congruence for Kloosterman sums mod 32, and then a necessary and sufficient condition for divisibility mod 32:

Theorem 5 [START_REF] Göloglu | Binary Kloosterman sums modulo 128 and coefficients of the characteristic polynomial[END_REF] Let q ≥ 32 and let a ∈ F q . Let e 1 , . . . , e 8 be the coefficients of the characteristic polynomial of a viewed as integers as described above. Then K q (a) ≡ 28e 1 + 8e 2 + 16(e 1 e 2 + e 1 e 3 + e 4 ) (mod 32).

Corollary 6 [START_REF] Göloglu | Binary Kloosterman sums modulo 128 and coefficients of the characteristic polynomial[END_REF] Let q ≥ 32 and let a ∈ F q . Let ē1 , . . . , ē4 ∈ F 2 be the coefficients of the characteristic polynomial of a. Then K q (a) ≡ 0 (mod 32) if and only if e 1 = 0, e 2 = 0, and e 4 = 0.

Next, a mod 64 congruence and characterisation:

Theorem 7 [START_REF] Göloglu | Binary Kloosterman sums modulo 128 and coefficients of the characteristic polynomial[END_REF] Let q ≥ 64 and let a ∈ F q . Let e 1 , . . . , e 8 be the coefficients of the characteristic polynomial of a viewed as integers as described above. Then K q (a) ≡28e 1 + 40e Corollary 8 [START_REF] Göloglu | Binary Kloosterman sums modulo 128 and coefficients of the characteristic polynomial[END_REF] Let q ≥ 64 and let a ∈ F q . Let ē1 , . . . , ē8 ∈ F 2 be the coefficients of the characteristic polynomial of a. Then K q (a) ≡ 0 (mod 64) if and only if the conditions of Corollary 6 are satisfied, and furthermore, e 8 = e 3 e 5 .

Finally we have a mod 128 congruence and characterisation:

Theorem 9 [START_REF] Göloglu | Binary Kloosterman sums modulo 128 and coefficients of the characteristic polynomial[END_REF] Let q ≥ 128 and let a ∈ F q . Let e 1 , . . . , e 16 ∈ {0, 1} be the coefficients of the characteristic polynomial of a viewed as integers as described above. Then K q (a) ≡92e 1 + 40e

Minimal polynomials of p-ary Kloosterman sums

As we mentioned before when p > 3 the Kloosterman sum is not necessarilly an integer. In this section, we give a result previously unpublished which proves a congruence for the minimal polynomial of p-ary Kloosterman sums over Q.

In this section we let p be an odd prime. Obviously K q (a) is an algebraic integer lying in the cyclotomic field Q(ζ). It is well known that

Gal(Q(ζ)/Q) = {ζ → ζ i | i ∈ (Z/pZ) * },
and it is easy to show (see [START_REF] Kononen | On integer values of Kloosterman sums[END_REF]) that the Galois automorphism ζ → ζ i has the effect K q (a) → K q (i 2 a), for any integer i. If we let

c a (x) = p-1 2 i=1 (x -K q (i 2 a))
it follows that c a (x) (which has degree (p-1)/2) is the characteristic polynomial of K q (a) over Q. If m a (x) is the minimal polynomial of K q (a) over Q, then

c a (x) = m a (x) ea
for some e a dividing p-1 2 . Most of the time, it is true that e a = 1. For example, Wan [START_REF] Qing | Minimal polynomials and distinctness of Kloosterman sums[END_REF] showed that Theorem 11 [START_REF] Qing | Minimal polynomials and distinctness of Kloosterman sums[END_REF] Let a ∈ F q . If Tr(a) = 0, the minimal polynomial of K q (a) has degree p-1 2 . Moisio [START_REF] Moisio | On certain values of Kloosterman sums[END_REF] considered the reduction of the minimal polynomial m a (x) modulo p. He showed that all coefficients, apart from the leading coefficient, are divisible by p.

In this section, our new result concerns the reduction of the minimal polynomial m a (x) modulo p 2 .

Theorem 12 Let p be an odd prime, and let • p be the Legendre symbol. Then

p-1 2 i=1 K q (i 2 a) ≡ p Tr(a) p (mod p 2 ) .
As a consequence, the constant term of the characteristic polynomial, which is

(-1) p-1 2 p-1 2 i=1 (K q (i 2 a)),
is always congruent to either 0 or ±p mod p 2 .

Thus if Tr(a) = 0, the minimal polynomial m(x) of K q (a) is precisely the characteristic polynomial c(x). In this case (and in the case that deg(m(x)) = p-1

2
where Tr(a) = 0) Theorem 12 gives a statement about the constant term of m(x) mod p 2 .

If Tr(a) = 0 and deg(m(x)) < p-1 2 , then the result in Theorem 12 is already known. In this case, our result gives us no extra information about the constant term of the minimal polynomial.

Ternary Kloosterman sums modulo 27

In the case that p = 3, Theorem 12 becomes the following theorem. This is precisely the modulo 9 characterisation of the ternary Kloosterman sum which we previously proved in [START_REF] Göloglu | Ternary Kloosterman sums modulo 18 using Stickelberger's theorem[END_REF].

The second previously unpublished result of this paper is to extend this result to a modulo 27 characterisation of ternary Kloosterman sums.

Theorem 13

 13 Let n > 1. For a ∈ F 3 n , K 3 n (a) ≡    0 (mod 9) if Tr(a) = 0, 3 (mod 9) if Tr(a) = 1, 6 (mod 9) if Tr(a) = 2.

  2 + 16(e 1 e 2 + e 4 ) + 80e 1 e 3 + 32(e 1 e 2 e 3 + e 1 e 7 + e 2 e 6 + e 8 )+ 96(e 1 e 2 e 4 + e 1 e 4 + e 1 e 5 + e 1 e 6 + e 2 e 3 + e 2 e 4 + e 3 e 5 )+ 64(e 1 e 2 e 3 e 4 + e 1 e 2 e 3 e 5 + e 1 e 2 e 5 + e 1 e 2 e 6 + e 1 e 2 e 10 + e 1 e 2 e 11 + e 1 e 2 e 12 + e 1 e 3 e 7 + e 1 e 3 e 11 + e 1 e 4 e 6 + e 1 e 4 e 7 + e 1 e 4 e 8 + e 1 e 4 e 10 + e 1 e 5 e 7 + e 1 e 5 e 9 + e 1 e 6 e 8 + e 1 e 8 + e 1 e 9 + e 1 e 10 + e 1 e 11 + e 1 e 12 + e 1 e 13 + e 1 e 14 + e 1 e 15 + e 2 e 3 e 5 + e 2 e 3 e 8 + e 2 e 3 e 9 + e 2 e 4 e 5 + e 2 e 4 e 6 + e 2 e 4 e 8 + e 2 e 5 e 7 + e 2 e 7 + e 2 e 8 + e 2 e 10 + e 2 e 12 + e 2 e 14 + e 3 e 4 e 5 + e 3 e 4 e 6 + e 3 e 4 + e 3 e 7 + e 3 e 10 + e 3 e 13 + e 3 + e 4 e 6 + e 4 e 8 + e 4 e 12 + e 5 e 6 + e 5 e 11 + e 6 e 10 + e 7 e 9 + e 16 ) (mod 128). Corollary 10 [4] Let q ≥ 128 and let a ∈ F q . Let ē1 , . . . , ē16 ∈ F 2 be the coefficients of the characteristic polynomial of a. Then K q (a) ≡ 0 (mod 128) if and only if the conditions of Corollary 8 are satisfied, and furthermore, e 16 ≡e 3 + e 3 (e 7 + e 10 + e 13 ) + e 5 (e 6 + e 11 )+ e 6 e 10 + e 7 e 9 (mod 2).

Trace and similar objects

Consider again the trace function Tr :

We wish to generalise this definition to a larger class of finite field sums, which includes the usual trace function as a special case. Definition 14 Let p be a prime, let n ≥ 1 be an integer and let q = p n . For any S ⊆ Z/(q -1)Z satisfying S p = S where S p := {s p | s ∈ S}, we define the function τ S : F q → F p by τ S (c)

Other than the set W , for the case p = 3, we will be particularly concerned with the following sets:

Result modulo 27

We use Gross-Koblitz formula and Fourier analysis (cf. [START_REF] Göloglu | Binary Kloosterman sums using Stickelberger's theorem and the Gross-Koblitz formula[END_REF]) to evalulate Gauss sums modulo 27 which gives us the following result.

Theorem 16 Let n ≥ 3, and let q = 3 n . Let Tr, τ X and τ Y be as defined in Section 4.1. Then We remark that a characterisation like in Theorem 16 of Kloosterman sums modulo p 3 for p > 3 does not seem to be straightforward. The estimates given by the Gross-Koblitz formula are weaker.


Antonia Wachter
email: antonia.wachter@uni-ulm.de

Valentin Afanassiev

Vladimir Sidorenko
email: vladimir.sidorenko@uni-ulm.de

Fast Decoding of Gabidulin Codes

A decoding algorithm for Gabidulin codes (defined over Fqm ) is shown that directly provides the evaluation polynomial using an equivalent of the Euclidean Algorithm. To obtain low complexity, a fast symbolic product and a fast symbolic division are presented. The achieved complexity of the whole decoding algorithm for Gabidulin codes is O(m 3 log m) operations over the ground field Fq.

Introduction

Gabidulin codes [START_REF] Gabidulin | Theory of Codes with Maximum Rank Distance[END_REF] are the rank metric analogues of Reed-Solomon (RS) codes. In [START_REF] Gabidulin | Theory of Codes with Maximum Rank Distance[END_REF], Gabidulin presented decoding based on a linearized equivalent of the Extended Euclidean Algorithm (LEEA). In [START_REF] Paramonov | An Analogue of Berlekamp-Massey Algorithm for Decoding Codes in Rank Metric[END_REF], [START_REF] Richter | Error and Erasure Decoding of Rank-Codes with a Modified Berlekamp-Massey Algorithm[END_REF], [START_REF] Sidorenko | Linearized Shift-Register Synthesis[END_REF], a generalization of the Berlekamp-Massey Algorithm (BMA) was given. The BMA and LEEA are used in the decoding process for solving a key equation. As a second step the socalled Gabidulin Algorithm (GA) has to be carried out, which can be seen as the rank metric analogue to calculating the error values. Loidreau formulated a Welch-Berlekamp-like Algorithm (WBA) that uses interpolation techniques [START_REF] Loidreau | A Welch-Berlekamp Like Algorithm for Decoding Gabidulin Codes[END_REF] and directly gives the linearized evaluation polynomial of the code. Hence, for the WBA no GA is necessary. The complexity of all these decoding methods is quadratic with the length of the code.

In [START_REF] Silva | Fast Encoding and Decoding of Gabidulin Codes[END_REF], a method for fast encoding and decoding of Gabidulin codes was presented, where the complexity of the two most demanding steps was reduced. Considering their complexity reduction, solving the key equation and the GA are the most complex steps.

In this contribution, we present a method to solve an alternative (transformed) key equation that directly outputs the evaluation polynomial using the LEEA. We use the accelerated LEEA from [START_REF] Wachter | A Fast Linearized Euclidean Algorithm for Decoding Gabidulin Codes[END_REF], which has complexity O(M(m) log m), where the Gabidulin code is defined over F q m and M(m) denotes the complexity of the symbolic product. To achieve a low overall complexity, we present a fast symbolic product and a fast symbolic division with complexity O(m 3 ) operations over the ground field F q using low-complexity normal bases. Since our algorithm does not require the GA afterwards, the complexity of the whole decoding process is accelerated to O(m 3 log m) operations over F q .

This paper is organized as follows: In Section 2, we give some preliminaries. Section 3 states the problem and in Section 4, we present the fast symbolic product and the fast symbolic division. Section 5 provides the decoding algorithm and Section 6 concludes this paper.

Preliminaries

Linearized Polynomials

Gabidulin codes are defined by means of linearized polynomials which were introduced by Ore [START_REF] Ore | On a Special Class of Polynomials[END_REF]. Let q be a power of a prime and let us denote the Frobenius q-power by x [i] = x q i where i is an integer. A linearized polynomial over the field

F q m is a polynomial of the form f (x) = d f i=0 f i x [i] , with f i ∈ F q m . If f d f = 0, we call deg q f (x) def = d f the q-degree of f (x). An important property of linearized polynomials ∀ α 1 , α 2 ∈ F q and ∀ a, b ∈ F q m is f (α 1 a + α 2 b) = α 1 f (a) + α 2 f (b).
The symbolic product of two linearized polynomials f (x) and g(x) is:

f (x) ⊗ g(x) = f (g(x)). (1)
Denote

deg q f (x) = d f and deg q g(x) = d g , then deg q (f (x) ⊗ g(x)) = d f + d g .
The symbolic product is associative and distributive, but in general noncommutative. The (usual) addition and the symbolic product convert the set of linearized polynomials into a non-commutative ring with identity element x [0] = x. Throughout this paper, all polynomials are linearized polynomials. We call b(x) a right symbolic divisor of a(x), if a(x) = q(x) ⊗ b(x) for some q(x). We denote the algorithmic calculation of the right symbolic division by q(x), rem(x) ← RDiv (a(x), b(x)), where rem(x) with deg q rem(x) < deg q a(x) denotes a possible remainder. Equivalently, b(x) is a left symbolic divisor of a(x), if a(x) = b(x) ⊗ q(x) and we denote the left symbolic division by q(x), rem(x) ← LDiv (a(x), b(x)).

The Linearized Euclidean Algorithm

Let r -1 (x) = a(x) and r 0 (x) = b(x) be two linearized polynomials with deg q a(x) ≥ deg q b(x). The LEEA with a stopping condition d S > 0 is given in Algorithm 1, where for the remainder deg q r i (x) < deg q r i-1 (x) holds. If d S = 1, the last nonzero remainder r j (x) is the so-called right symbolic greatest common divisor rsgcd(a(x), b(x)). With the additional polynomials u i (x), v i (x), we can rewrite each remainder:

r i (x) = v i (x) ⊗ a(x) + u i (x) ⊗ b(x), ∀i. (2)
Algorithm 1: LEEA (Linearized Extended Euclidean Algorithm)

Input: a(x), b(x) with deg q a(x) ≥ deg q b(x), Stopping Degree d S Initialize: r -1 (x) ← a(x), r 0 (x) ← b(x), i ← 1, u -1 (x) = 0, u 0 (x) = x [0] , v -1 (x) = x [0] , v 0 (x) = 0 while deg q r i-1 (x) ≥ d S do 1 q i (x), r i (x) ← RDiv (r i-1 (x), r i-2 (x)) 2 u i (x) ← u i-2 (x) -q i (x) ⊗ u i-1 (x) 3 v i (x) ← v i-2 (x) -q i (x) ⊗ v i-1 (x) 4 i ← i + 1 5 Output: r i-1 (x), u i-1 (x), v i-1 (x)

Normal Bases

A basis B = {β 0 , β 1 , . . . , β m-1 } of F q m over F q is a normal basis if β i = β [i]
for all i and β ∈ F q m is called a normal element. There is a normal basis of F q m over F q for any prime power q and any positive integer m [START_REF] Gao | Normal Bases over Finite Fields[END_REF]. A basis

B = { β 0 , β 1 , . . . , β m-1 } of F q m over F q is called a dual basis to B if Tr( β i β j ) is
equal to 1 for i = j and 0 in all other cases. The dual basis of a normal basis is again a normal basis [START_REF] Gao | Normal Bases over Finite Fields[END_REF].

If B = B, it is called a self-dual normal basis. In a normal basis B, the product of a, b ∈ F q m is usually done as follows. We represent a = m-1 i=0 a (i) β i , b = m-1 i=0 b (i) β i with all a (i) , b (i) ∈ F q and a = (a (0) . . . a (m-1) ), b = (b (0) . . . b (m-1) ) denote the vector representations. A multiplication table T ∈ F m×m q
is defined such that [START_REF] Gao | Normal Bases over Finite Fields[END_REF]: →i , where the arrows denote a cyclic shift of the vector by i positions to the right/left. The number of non-zero entries of T is called complexity C(T) and is lower bounded by C(T) ≥ 2m -1. Low-complexity normal bases (i.e., C(T) ≈ 2m) exist in many cases, e.g. for q = 2 s if gcd(m, s) = 1 and 8 ∤ m. For q = 2 s and odd m, all these low-complexity normal bases are self-dual (see also [START_REF] Gao | Normal Bases over Finite Fields[END_REF]).

β 0 • ( β 0 β 1 . . . β m-1 ) T = T • ( β 0 β 1 . . . β m-1 ) T . This is used to calculate the product a • b = m-1 i=0 b (i) (a ←i T)
For a normal basis B, the q-transform of a linearized polynomial f (x) is:

Definition 1 (q-Transform [START_REF] Silva | Fast Encoding and Decoding of Gabidulin Codes[END_REF]). The q-transform of a vector f ∈ F m q m (or a linearized polynomial f (x) with deg q f (x) < m) with respect to a normal element β is the vector

(F 0 F 1 . . . F m-1 ) ∈ F m q m (or F (x) = m-1 j=0 F j x [j]
), given by

F j = f (β [j] ) = m-1 i=0 f i β [i+j] , j = 0, . . . , m -1. (3)
Using the multiplication table,

F j = m-1 k=0 m-1 i=0 f (i) k (T j+k-i ) →i , where f k = (f (0) k . . . f (m-1) k
) is the vector representation of f k over F q and T j+k-i is the (j + k -i)-th row of T. Here, the index ℓ of T ℓ is calculated mod m.

Theorem 1 (Inverse q-Transform [START_REF] Silva | Fast Encoding and Decoding of Gabidulin Codes[END_REF]). The inverse q-transform of a vector

(F 0 F 1 . . . F m-1 ) ∈ F m q m (or a linearized polynomial F (x)) with resprect to β is given by f i = F ( β [j] ) = m-1 j=0 F j β [j+i] , j = 0, . . . , m -1, where B = { β 0 , . . . , β m-1 }, is dual to B.

Complexity of Elementary Operations

For simplicity, throughout this paper, let us consider only self-dual normal bases, i.e., β i = β i = β [i] . In a normal basis representation, q-exponentiations are only cyclic shifts and hence the complexity of the Frobenius powers is negligible. The product a • b of any two elements a, b ∈ F q m can be calculated by the multiplication table T with complexity O(m 2 ) operations over F q . The calculation of the (inverse) q-transform (3) requires at most (m -1)mC(T) additions over F q , i.e., in the order of O(m 3 ) operations over F q [START_REF] Silva | Fast Encoding and Decoding of Gabidulin Codes[END_REF].

Let M(n) denote the complexity of calculating the symbolic product (1) where n = max{d f , d g }. The complexity of the (right/left) symbolic division will be denoted by D(n). With standard implementation, the complexity of both is in the order of O(n 2 ) operations over F q m [3]. In Section 4, we give fast algorithms for calculating the symbolic product and division.

In [START_REF] Wachter | A Fast Linearized Euclidean Algorithm for Decoding Gabidulin Codes[END_REF], a fast LEEA was presented which achieves complexity

O(M(n) log n) if n ≥ deg q a(x) ≥ deg q b(x).

Gabidulin Codes

Definition 2 (Gabidulin Code [START_REF] Gabidulin | Theory of Codes with Maximum Rank Distance[END_REF]). A linear G(n, k) Gabidulin code over F q m for n ≤ m is the set of all codewords, which are the evaluation of a q-degree restricted linearized polynomial:

G(n, k) def = {c = (f (α 0 ), f (α 1 ), . . . , f (α n-1 )| deg q f (x) < k)},
where the fixed elements α 0 , . . . , α n-1 ∈ F q m are linearly independent over F q .

If we use the basis elements α i = β [i] as evaluation points (where β is a normal element), the codeword c(x) is the inverse q-transform of the corresponding f (x).

Given a basis B of F q m over F q , there exists a one-to-one mapping for each vector x ∈ F n q m on a matrix X ∈ F m×n q . Let the rank norm rank q (x) be the rank of X over F q . The minimum rank distance d of a code G is defined by

d = min{rank q (c) | c ∈ G, c = 0}. Gabidulin codes are Maximum Rank Distance (MRD) codes, i.e., d = n -k + 1.
Let c be the transmitted codeword that is corrupted by an additive error vector e ∈ F n q m of rank q (e) = t. The received vector r ∈ F n q m is r = c + e. We can use a t × n matrix Y ∈ F t×n q of rank t to decompose the error:

e = x • Y = (x 1 x 2 . . . x t ) • Y, (4)
with x 1 , x 2 , . . . , x t ∈ F q m are linearly independent over F q . Note, that this decomposition into x and Y is not unique.

Let e(x), r(x) denote the error and received word as linearized polynomials. Let E(x), R(x) denote the q-transform of e(x), r(x), where R(x) = f (x) + E(x).

Classical decoding of Gabidulin codes mainly consists of two steps: First, a key equation has to be solved to determine x (4). Second, the matrix Y (4) has to be calculated to reconstruct the error. However, using Loidreau's WBA or our new approach, we directly obtain the evaluation polynomial f (x).

Solving the key equation is equivalent to finding an error span polynomial Λ(x) that contains all linear combinations of x 1 , x 2 , . . . , x t (4) as roots. We use an alternative key equation [START_REF] Silva | Fast Encoding and Decoding of Gabidulin Codes[END_REF] for our algorithm. Note that there should be a similar relation as for Reed-Solomon codes between (5) and Loidreau's WBA.

Theorem 2 (Transformed Key Equation [START_REF] Silva | Fast Encoding and Decoding of Gabidulin Codes[END_REF]). Let E(x) be the q-transform (3) of the error word e(x), then the linearized error span polynomial Λ(x) satisfies

Λ(x) ⊗ E(x) ≡ 0 mod (x [m] -x), (5)
where

deg q Λ(x) = t ≤ ⌊(n -k)/2⌋.

Problem Formulation

To obtain a low-complexity decoding algorithm, we need a fast symbolic product (1) and a fast symbolic division.

Problem 1 (Fast Symbolic Product). Let two linearized polynomials f (x), g(x) over F q m with q-degrees d f , d g be given. Find with subquadratic complexity a linearized polynomial h(x), such that

h(x) = d f +dg i=0 h i x [i] = f (x) ⊗ g(x) mod (x [m] -x) = f (g(x)) mod (x [m] -x).
Problem 2 (Fast Symbolic Division). Let two linearized polynomials a(x), b(x) over F q m be given. Find with subquadratic complexity r(x) and q(x), such that for the right symbolic division a(x) = q(x) ⊗ b(x) + r(x), where deg q r(x) < deg q b(x),

or for the left symbolic division a(x) = b(x) ⊗ q(x) + r(x), where deg q r(x) < deg q b(x).

The problem of solving the transformed key equation is as follows.

Problem 3 (Solving Transformed Key Equation). Given R(x) as the q-transform (3) of the received word r(x) with rank distance ≤ ⌊(n -k)/2⌋ from a codeword from G(n, k), find the linearized error span polynomial Λ(x) and the linearized evaluation polynomial f (x) such that

Λ(x) ⊗ E(x) = Λ(x) ⊗ (R(x) -f (x)) ≡ 0 mod (x [m] -x), (6)
where deg q Λ(x) = t ≤ ⌊(n -k)/2⌋.

Fast Symbolic Product and Division

In order to calculate the symbolic product (1) and the symbolic division efficiently, we give two approaches. The first uses similar transform-based ideas as in [START_REF] Gabidulin | Kodirovanie v radioelektronike (Coding in Radio Electronics)[END_REF] and the second uses directly the normal basis representation for the multiplication of two elements. By means of low-complexity normal bases, we achieve the smallest known complexity for solving Problems 1 and 2.

Transform-Based Fast Symbolic Product

Algorithm 2 calculates the symbolic product h(x) = f (g(x)) mod (x [m] -x) in three main steps. It is based on the fact that the coefficients of H(x) can be calculated by

H i = h(β [i] ) = f (g(β [i] )), where H(x) is q-transform of h(x) (3)
.

Algorithm 2: Fast Symbolic Product

Input: Linearized polynomials f (x), g(x)
Calculate the q-transform of g(x): G i = g(β [i] ) for i = 0, . . . , m -1 (3)

1 Calculate H i = f (G i ) for i = 0, . . . , m -1, H(x) = m-1 i=0 H i x [i] 2 Calculate inverse q-transform of H(x): h i = H(β [i] ) for i = 0, . . . , m -1 3 Output: Symbolic product h(x) = m-1 i=0 h i x [i]
Steps 1 and 3 are (inverse) q-transforms, which require complexity O(m 3 ) over F q using low-complexity normal bases (see Section 2.3).

Step 2 corresponds to the following general problem of multipoint-evaluation of a linearized polynomial.

Problem 4 (Multipoint Evaluation of a Linearized Polynomial). Given a linearized polynomial f (x) over F q m , find the evaluation values f (G 0 ), f (G 1 ), . . . , f (G m-1 ), where G 0 , . . . , G m-1 are arbitrary elements from F q m . This problem can be solved as follows. We represent

G i = m-1 j=0 γ (i) j • β [j]
, with γ (i) j ∈ F q for all 0 ≤ i, j ≤ m -1. Since α [k] = α for any α ∈ F q and all k:

f (G i ) = f m-1 j=0 γ (i) j • β [j] = m-1 j=0 γ (i) j • f β [j] .
All m evaluation values can be calculated by

f (G 0 ) f (G 1 ) . . . f (G m-1 ) = f (β [0] ) f (β [1] ) . . . f (β [m-1] ) •       γ (0) 0 γ (1) 0 . . . γ (m-1) 0 γ (0) 1 γ (1) 1 . . . γ (m-1) 1 . . . . . . . . . . . . γ (0) m-1 γ (1) m-1 . . . γ (m-1) m-1       . (7)
Also, we represent f (β

[i] ) = m-1 j=0 f (i) j • β [j] , with f (i) j ∈ F q , for all 0 ≤ i, j ≤ m -1.
Hence, we obtain:

f (G 0 ) f (G 1 ) . . . f (G m-1 ) def = β • F • G = β [0] β [1] . . . β [m-1] •      f (0) 0 f (1) 0 . . . f (m-1) 0 f (0) 1 f (1) 1 . . . f (m-1) 1 . . . . . . . . . . . . f (0) m-1 f (1) m-1 . . . f (m-1) m-1      •      γ (0) 0 . . . γ (m-1) 0 γ (0) 1 . . . γ (m-1) 1 . . . . . . . . . γ (0) m-1 . . . γ (m-1) m-1      .
Thus, Problem 4 can be solved by Algorithm 3. Calculate the q-transform of f (x):

F i = f (β [i] ) for i = 0, . . . , m -1 (3) 1 Calculate representation of F (x) over F q : f (i) j , 0 ≤ i, j ≤ m -1 2 Calculate F • G. 3 Output: f (G 0 ), . . . , f (G m-1 )
Step 1 is a q-transform and requires complexity O(m 3 ) over F q .

Step 2 requires no complexity since the representation over F q is given. Finally, Step 3 consists of multiplying two m × m matrices over F q which is done with at most O(m 3 ) operations over F q and Algorithms 2 and 3 have complexity O(m 3 ) over F q .

Direct Fast Symbolic Product

Recall that in a normal basis representation, the multiplication c = a • b ∈ F q m is done in the representation over the ground field by c = m-1 i=0 b (i) (a ←i T) →i . The multiplication of an element a ∈ F q m and an element of the normal basis β i = β [i] is done by (a ←i T) →i with complexity O(m) over F q .

To calculate the symbolic product h(x) = f (g(x)) mod (x [m] -x) (1), let us denote n = min{deg q h(x), m} and the representation of elements over F q by

f j = (f (0) j . . . f (m-1) j
) and analogously, we denote g j . Note that a cyclic shift to the right by i positions is denoted by g j →i and corresponds to the representation of g

[i]

j ∈ F q m over the ground field F q . The coefficients of the symbolic product can then be written by

h ℓ = n-1 j=0 f j g [j] ℓ-j = n-1 j=0 m-1 i=0 g (i)→j ℓ-j • (f j ←i T) →i , ∀ℓ = 0, . . . , n -1.
Note that the calculation of (f j ←i T) →i is the same for all ℓ. Hence, we calculate it for all i = 0, . . . , m -1 and j = 0, . . . , n -1 with complexity O(nm 2 ) over F q . Then, we sum up for each ℓ = 0, . . . , n -1, which consists each time of nm multiplications over F q . Hence, the sum is calculated with complexity O(n 2 m) operations over F q and all coefficients of the symbolic product are calculated with complexity O(nm 2 ) over F q . This approach is favorable to the transform-based approach if n < m.

Complexity Analysis

Algorithm 4 consists of three steps. As explained in Section 2.4, the q-transform can be calculated with complexity O(m 3 ) over F q if low-complexity normal bases are used. For the second step, we can use the fast LEEA from [START_REF] Wachter | A Fast Linearized Euclidean Algorithm for Decoding Gabidulin Codes[END_REF] which has complexity O(M(m) log m). This fast LEEA is based on the Divide and Conquer principle and in its recursions, the polynomials have very small q-degree. Hence, we use the direct fast symbolic product from Section 4.2, since its complexity depends on the q-degree of the input polynomials. Thus, the second step has complexity O(m 3 log m) over F q . The third step of Algorithm 4 is a linearized division, which can be done with complexity O(m 3 ) over F q using the ideas from Section 4. Hence, the overall decoding complexity is O(m 3 log m) over F q .

Conclusion

We showed a method for fast decoding of Gabidulin codes. The decoding algorithm uses an equivalent of the Euclidean Algorithm and directly yields the evaluation polynomial of the code. By means of a fast symbolic product and division, the complexity of the whole decoding process is accelerated to O(m 3 log m) operations over the ground field F q .

Algorithm 3 :

 3 Multipoint Evaluation of a Linearized PolynomialInput: Linearized polynomial f (x), Evaluation points G 0 , . . . , G m-1

⋆ This work was supported by the German Research Council "Deutsche Forschungsgemeinschaft" (DFG) under Grant No. Bo867/21-1. V. Sidorenko is on leave from IITP, Russian Academy of Sciences, Moscow, Russia.

Fast Symbolic Division

The fast symbolic division uses similar ideas as the fast (tranformed) symbolic product and will be described only shortly. We can rewrite [START_REF] Ore | On a Special Class of Polynomials[END_REF] by β [0] . . . β [m-1] • H = β [0] . . . β [m-1] • F • G, where H ∈ F m×m q denotes the representation of (H 0 H 1 . . . H m-1 ) = (f (β [0] ) . . . f (β [m-1] )) over the small field.

For the right symbolic division, H and G are known and for the left symbolic division, H and F are known. We have to solve H = F • G for G or F. This requires at most complexity O(m 3 ) over F q and the (right/left) symbolic division can also be accomplished with complexity O(m 3 ) over F q .

5 Solving the Transformed Key Equation 5.1 Idea and Algorithm Equation ( 6) can be rewritten with some polynomial Ω(x):

Comparing this equation to (2), we obtain Algorithm 4. We can run the LEEA with the input polynomials (x [m] -x) and R(x) and the stopping condition

and we can find f (x) by a (fast) left symbolic division. Otherwise, the remainder of the symbolic division will be unequal to zero, and we return decoding failure.

This algorithm can also be seen as a generalization of the Gao Algorithm for Reed-Solomon codes [START_REF] Gao | A New Algorithm for Decoding Reed-Solomon Codes[END_REF] for linearized polynomials. Calculate R(x) as the q-transform of r(x) (3)

The following theorem proves the correctness of our algorithm. Proof (Sketch). If t = rank q (rc) ≤ ⌊(n -k)/2⌋, there is a unique solution of (6) (except for a constant factor), where deg q f (x) < k and deg q Λ(x) = t. We show that Algorithm 4 finds exactly this minimal-degree solution.

Due to (2), for each step of LEEA(x [m] -x, R(x))

holds and because of our stopping condition, for the output of the LEEA deg q r i (x) < ⌊(n + k)/2⌋ and deg q u i (x) ≤ ⌊(n -k)/2⌋. Assume the LEEA does not find the solution of minimal degree, i.e., we obtain a second solution such that:

the following has to hold with some polynomial b(x):

And hence, for the second solution we have:

If this was a result of LEEA(x [m] -x, R(x)), then in this step u i (x) = b(x) ⊗ Λ(x) and v i (x) = b(x) ⊗ Ω(x). Since u i (x) and v i (x) have to be symbolically relatively prime, b(x) is a scalar and Algorithm 4 finds the unique solution except for a constant factor.

On the other hand assume t > ⌊(n -k)/2⌋ and Algorithm 4 returns f (x) with deg q f (x) < k. In last step of the LEEA, the following holds:

and hence also

Due to the stopping condition, deg q u i (x) ≤ ⌊(n -k)/2⌋ and u i (x) can have at most ⌊(n -k)/2⌋ linearly independent roots. Hence, r j = c j for at least n -⌊(n -k)/2⌋ values of j. Therefore, there exists a c such that rank q (rc) ≤ ⌊(n -k)/2⌋. This is a contradiction and Algorithm 4 fails if the rank distance of r is greater than ⌊(n -k)/2⌋ to any codeword. ⊓ ⊔


Annika Meyer

On the number of lattice points in a small sphere

. Examples where the obtained bounds are optimal include some root lattices in small dimensions and the Leech lattice. We also present a natural decoding algorithm for lattices constructed from lattices of smaller dimension, and apply our results on the number of lattice points in a small sphere to conclude on the performance of this algorithm.

Introduction

A lattice L in R n is the set of all integral linear combinations of a basis (b 1 , . . . , b n ) of R n , i.e.

L = {z 1 b 1 + • • • + z n b n | z 1 , . . . , z n ∈ Z}.
In this paper we give upper bounds on the number of lattice points contained in a closed ball B r (z) := {v ∈ R n | |v -z| ≤ r} where z is any vector in R n and | . | is the usual Euclidian length. In the special case where L = Z 2 is the standard lattice in R 2 and z is a lattice point, the cardinality of B r (z) ∩ L is the subject of Gauss's circle problem, whose solution is well known (see [START_REF] Cohn-Vossen | Geometry and the imagination[END_REF], for instance). Moreover, there exist good asymptotic estimates for |B r (z) ∩ L|, i.e. as r goes to infinity (cf. [START_REF] Chamizo | On the sphere problem[END_REF][START_REF] Heath-Brown | Lattice points in the sphere[END_REF][START_REF] Tsang | Counting lattice points in the sphere[END_REF]). However, very little seems to be known for small values of r. To the author's knowledge, the only work that has been done so far is by Conway and Sloane, who in [START_REF] Conway | On the covering multiplicity of lattices[END_REF] give a lower bound on |B √ µ(L) (z) ∩ L|, provided that z is not exactly at distance µ(L) from any lattice point. Here is the (squared) covering radius of L.

The first method we use to upper bound |B r (z) ∩ L| resembles the one used by Conway and Sloane in [START_REF] Conway | Sphere packings, lattices and groups[END_REF]Ch.13] to upper bound the kissing number of a lattice (i.e. the number of its shortest nonzero vectors). Let min(L) := min 0 =l∈L |l| 2 be the minimum of L. If min(L) 4 ≤ r 2 ≤ min(L) then Theorem 1 shows that the lattice points in B r (z) can be rearranged inside B r (z) as a spherical code with a certain minimum angle. Recall that a spherical code C with minimum angle θ is just a set of points lying on the boundary of a sphere centered anywhere, at v, say, such that the angle between vc and vc ′ is at least θ, for any two distinct points c, c ′ ∈ C. This gives rise to upper bounds on |B r (z) ∩ L|, since there exist various methods to upper bound the cardinality of a spherical code with a given minimum angle. The most general approach uses linear programming.

The key idea for the linear programming method is given in Lemma 1, but for a more detailed treatment, we refer the reader to [START_REF] Conway | Sphere packings, lattices and groups[END_REF]Ch.13]). Calculations using this linear programming method are summarized in Table 4 for some important lattices, such as root lattices in dimension up to 10 and the Leech lattice, for r = µ(L). This choice of r is motivated by the coding theoretic application in Section 5. In some cases the upper bound on |B √ µ(L) (z) ∩ L| is attained when z is a deep hole of L, that is, min l∈L |z -l| 2 = µ(L). This shows that in the respective cases, these bounds are optimal, and moreover, the lattice points at distance µ(L) from a deep hole of L form an optimal spherical code with the respective minimum angle.

To also obtain upper bounds on |B r (z) ∩ L| when r 2 > min(L), we present a different approach in Section 3, based on Gaussian-like measures on L. For each z ∈ R n Theorem 2 gives a positive real number γ r,L,z such that |B r (z) ∩ L| ≤ γ r,L,z . Based on worst-case assumptions on z, we also obtain a universal upper bound, i.e. a positive real γ r,L such that sup

z∈R n |B r (z) ∩ L| ≤ γ r,L . (1)
The bounds obtained for r = µ(L) are also in Table 4.

The results show that in general neither of the two methods to upper bound |B r (L) ∩ L| is superior to the other. Moreover, our observations let us conjecture the following. From our calculations, summarized in Table 4, we can verify this conjecture in some cases, as follows.

Remark 1. The lattices A n (n ∈ {2, 3, 4}), D n (n ∈ {3, 4, 5}), E n (n ∈ {6, 7, 8}) and the Leech lattice Λ 24 satisfy Conjecture 1.

In Section 5 we give a coding theoretic application of our results. Lattices are used as codebooks in important modern communication systems, like MIMO fading channels (cf. [START_REF] Caire | Lattice coding and decoding achieve the optimal diversity-multiplexing tradeoff of MIMO channels (English summary)[END_REF][START_REF] Caire | On maximum-likelihood detection and the search for the closest lattice point (English summary)[END_REF]). In this context decoding a received signal z ∈ R n means finding the lattice point closest to z, i.e. finding l ∈ L such that |z -l| ≤ |z -l| for all l ∈ L. This problem is commonly called the Closest Vector Problem and is hard to solve in general (see [START_REF] Guruswami | The complexity of the covering radius problem[END_REF] for a study of the complexity of this problem).

In this paper we give an algorithm that solves the closest vector problem approximately in lattices with a certain structure. Here approximately means that, given z ∈ R n , our algorithm finds a lattice point l ∈ L such that |z -l| ≤ γ • |z -l| for all l ∈ L, where γ > 1 is a real number which does not depend on z.

The lattices considered in this paper are given in the following form. Given positive integers n i for i ∈ {0, . . . , t}, and lattices W i in R ni as well as linear maps

f i : R n0+•••+ni-1 → R ni , i ∈ {1, . . . , t}, with f 1 = 0, consider the lattice L given by {(u 1 , . . . , u t ) ∈ R n1+•••+nt | u i -f i (u 0 , . . . , u i-1 ) ∈ W i , i ∈ {1, . . . , t}}.
For example, lattices obtained from Turyn's construction (cf. Chapter 8 of [START_REF] Conway | Sphere packings, lattices and groups[END_REF]) are obtained in this way (see Lemma 4). These include very well known lattices such as the Leech lattice and the recently found extremal unimodular even lattice in dimension 72 (cf. [START_REF] Nebe | An even unimodular 72-lattice with minimum 8[END_REF]).

The recursive definition of the points in L allows to approximate a vector (z 1 , . . . , z t ) ∈ R n1+•••+nt by successive approximations in W i . An algorithm to do this is given in Section 5. It is a generalisation of Babai's Nearest Plane Method (cf. [START_REF] Babai | On Lovász' lattice reduction and the nearest lattice point problem[END_REF]), using the Fincke-Pohst method (also called sphere decoding, cf. [START_REF] Fincke | Improved methods for calculating vectors of short length in a lattice, including a complexity analysis[END_REF]) as a subroutine to obtain all points of W 1 in a certain small sphere B around z 1 first. The approximation factor is given in Remark 2. The additional effort to our algorithm stemming from dealing with all the points of W 1 contained in B depends of course on |B ∩ W 1 | and can be estimated using the results in the previous sections. We then apply the algorithm to lattices obtained from Turyn's construction. In particular, we conclude on the performance of the algorithm in the case of the newly found extremal even unimodular lattice in dimension 72 (see [START_REF] Nebe | An even unimodular 72-lattice with minimum 8[END_REF]).

Bounds on |B r (z) ∩ L| via spherical codes

Let L be a lattice in R n , and assume (possibly after rescaling) that L has covering radius 1. Let z be a deep hole of L. Then the lattice points in B := B 1 (z) all lie on the border of the unit ball B; in other words, they form a spherical code C. Since any two different elements of C are at least min(L) 1 2 apart, the angle θ between them satisfies

θ ≥ 2 sin -1 ( min(L) 2 ).
This observation is generalized in Theorem 1, which states that for every ball

B r (z) with r 2 ∈ [ min(L) 4
, min(L)] centered at any point z ∈ R n , the lattice points contained in that ball give rise to a spherical code with a certain minimum angle.

In what follows let A(n, θ) be the maximal cardinality of a spherical code in dimension n and with minimum angle at least θ.

Theorem 1. Let L be a lattice in R n and let r be a positive real such that min(L) 4

≤ r 2 ≤ min(L). Then for any z ∈ R n -L, the set

{|x -z| -1 (x -z) | x ∈ B r (z) ∩ L} is a spherical code with minimum angle cos -1 (1 -min(L) 2r ). In particular |B r (z) ∩ L| ≤ A(n, cos -1 (1 -min(L) 2r )).
Proof. After rescaling L with r -1 , assume that r = 1, and hence min(L) ≥ 1.

For any x, y ∈ B 1 (z) ∩ L, we aim to lower bound the angle θ between xz and yz. Observe that

|x -z| 2 + |y -z| 2 -2 cos(θ)|x -z| |y -z| = |x -y| 2 .
Since |x -y| 2 ≥ min(L), this yields

cos(θ) ≤ |x -z| 2 + |y -z| 2 -min(L) 2|x -z| |y -z| . (2)
Now for a ∈ (0, 1] consider the real function

f a : t → a 2 +t 2 -min(L) 2at
. This function is decreasing since for any real t,

δf δt (t) = t 2 -a 2 + min(L) 2at 2 ≥ 0.
For symmetry reasons, it follows that the right hand side of ( 2) is maximised if |x -z| = |y -z| = 1. In this case, equation (2) yields cos(θ) ≤ 1 -min(L)

2

, which shows the assertion.

The lemma below follows from Theorem 1 together with [START_REF] Conway | Sphere packings, lattices and groups[END_REF]Ch.13]. Since the proof is analogous to the one provided in [START_REF] Conway | Sphere packings, lattices and groups[END_REF], we shall omit it here. Lemma 1. Let L be a lattice in R n with µ(L) ≤ min(L) and let f be a real polynomial of degree d satisfying the following conditions:

(i) f (t) ≤ 0 for -1 ≤ t ≤ 1 -2 min(L) µ(L) , (ii) if f (t) = d i=0 f i P α,α i is the expansion of f in terms of Jacobi polynomials, with α = n-3
2 , then f 0 > 0 and f i ≥ 0 for i ∈ {1, . . . , d}.

Then |B µ(L) (z) ∩ L| ≤ f (1) f0 for every z ∈ R n .
Note that a polynomial f as in Lemma 1 can be found by linear programming -again, see [START_REF] Conway | Sphere packings, lattices and groups[END_REF]Ch.13] for an explanation.

3 Bounds on |B r (z) ∩ L| via Gaussian measures on L Let L be a lattice in R n and let

L ♯ := {v ∈ R n | (v, l) ∈ Z for all l ∈ L} be its dual lattice, where (•, •) : R n × R n , (v, w) → v 1 w 1 + • • • + v n w n is the standard scalar product on R n .
The main idea in this section is to use the Schwartz function f : R n → R, x → e -π(x,x) as a kind of measure on L as well as on its translate Lu := {lu | l ∈ L} to upper bound |B r (u) ∩ L| (see also [START_REF] Banaszczyk | New bounds in some transference theorems in the geometry of numbers[END_REF]).

Theorem 2. Let L be a lattice in R n and let z ∈ R n . For every positive real r and every δ > ( n 2π )

1 2 we have |L ∩ B r (z)| ≤ γ r,L,z , where γ r,L,z = e πr 2 det(L) -1 2 y∈L ♯ ∩B δ (0) cos(2π(z, y))f (y) R δ .
Moreover, for any z ∈ R n we have γ r,L,z ≤ γ r,L , where

γ r,L = e πr 2 x∈L∩B δ (0) f (x) R δ .
The error term is

R δ = (1 -(δ( 2π n ) 1 2
) n e n 2 -πδ 2 ) -1 and tends to 1 as δ goes to infinity.

For the proof of Theorem 2 we need the two lemmata below. The following improves [2, Lemma 1.4(ii)].

Lemma 2. With f as above, we have

x∈L-z f (x) = det(L) -1 2 y∈L ♯ cos(2π(z, y))f (y) ≤ x∈L f (x).
Proof. Our proof uses the Poisson summation formula for lattices, which states for any lattice L in R n and a sufficiently well-behaved function g : R n → C,

x∈L g(x) = det(L) -1 2 y∈L ♯ ĝ(y),
where ĝ : R n → C, y → R n e 2πi(x,y) g(x)dx is the Fourier transform of g. Now the functions f and its translate x → f (xz) are sufficiently wellbehaved, and f is its own Fourier transform, wheras the Fourier transform of the translate is y → e 2πi(z,y) f (y). Hence Poisson summation yields

x∈L-z f (x) = x∈L f (x -z) = det(L) -1 2 y∈L ♯ exp(-2πi(z, y))f (y) = det(L) -1 2 (1 + {y,-y}⊆L, y =0 2 cos(2π(z, y))f (y) = det(L) -1 2 y∈L ♯ cos(2π(z, y))f (y) ≤ det(L) -1 2 y∈L ♯ f (y) = x∈L f (x).

Lemma 3. [(cf. [2, Lemma 1.5(ii)])]

For any lattice L in R n and for each δ > n 2π

1 2 we have

x∈L-B δ (0) f (x) < (δ( 2π n ) 1 2 ) n e n 2 -πδ 2 x∈L f (x).
Proof of Theorem 2. Consider the inequality chain

|L ∩ B r (z)| e -πr 2 ≤ x∈L-z f (x) = det(L) -1 2 y∈L ♯ cos(2π(y, z))f (y).
The first inequality simply stems from the fact that |L∩B r (z

)| = |L-z ∩B r (0)|.
The second inequality follows from Lemma 2. Now take any δ > n 2π 1 2 , then the right hand side of the above is at most

det(L) -1 2 ( y∈L ♯ ∩B δ (0) cos(2π(y, z))f (y) + y∈L ♯ -B δ (0) f (y)) ≤ det(L) -1 2 y∈L ♯ ∩B δ (0) cos(2π(y, z))f (y)R δ ≤ x∈L∩B δ (0) f (x)R δ ,
where the last two inequalities are due to Lemma 3. This proves the theorem.

Results for some important lattices

The following table lists some important lattices L (see [START_REF] Conway | Sphere packings, lattices and groups[END_REF] for a definition of these lattices). If Theorem 1 applies with r = µ(L) then the minimal angle of the obtained spherical code is denoted θ; an upper bound on sup z∈R n |B √ µ(L) (z)∩L| is hence given by A(n, θ). To upper bound A(n, θ), the author implemented the linear programming method described in [START_REF] Conway | Sphere packings, lattices and groups[END_REF]Ch.13] in MAGMA ( [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF]), obtaining a polynomial f as in Lemma 1. The coefficients of f in the expansion in terms of Jacobi polynomials are given in the fourth column, rounded to three decimal places, as a sequence [f 0 , . . . , f d ], meaning that f (t) = f 0 P α,α

0 (t)+• • •+f d P α,α d (t)
, where α and d are as in Lemma 1.

The penultimate column gives the bound obtained by the method described in Section 3. Note that it may be convenient to rescale the lattices to obtain better results. The author observed that in many cases the best results are obtained when the lattice is rescaled as to be of minimum 1. The last column of the table gives the the maximal number |B √ µ(L) (u) ∩ L| attained at a deep hole u of L.

A recursive decoding algorithm for certain lattices

In this section we describe a recursive decoding algorithm for lattices obtained from lattices of smaller dimension by a procedure resembling the gluing method (see [START_REF] Conway | Sphere packings, lattices and groups[END_REF]Ch.4]). We show that among these lattices, there are those obtained from Turyn's construction. Hence in particular our algorithm applies to the Leech lattice and to the recently found extremal even unimodular lattice in dimension 72 ( [START_REF] Nebe | An even unimodular 72-lattice with minimum 8[END_REF]).

The lattices considered here are of the following form: Let n 0 , . . . , n t be positive integers and let W 1 , . . . , W t be lattices in R ni . Moreover, let

f i : R n0+•••+ni-1 → R ni
be linear maps, for i ∈ {1, . . . , t}, where f 1 = 0. Let n := n 1 + • • • + n t . Then we define L = L(W 1 , . . . , W t , f 2 , . . . , f t ) as

L := {(u 1 , . . . , u t ) ∈ R n | u i -f i (u 0 , . . . , u i-1 ) ∈ W i (i = 1, . . . , t)}.
Clearly L is a lattice in R n . We propose the following algorithm to find a point nearby a given vector in R n in a lattice L as above.

Algorithm A: Input: A vector z := (z 1 , . . . , z t ) ∈ R n (where z i ∈ R ni for i ∈ {1, . . . , t}) and a lattice L as above.

( 1 ) Use sphere decoding to find all points in W 1 ∩ B √ µ(W1) (z 1 ). ( 2) For every point w 1 found in step (1) do the following. Put x 0 := 0 and x 1 := w 1 . Successively, approximate z i -f i (x 0 , . . . , x i-1 ) by a point w i ∈ W i and put x i := w i + f i (x 0 , . . . , x i-1 ). Then x := (x 1 , . . . , x t ) ∈ L.

( 3 ) Among all approximations found in step [START_REF] Banaszczyk | New bounds in some transference theorems in the geometry of numbers[END_REF], choose the best one. Remark 2. Let x be the approximation of z found by the above algorithm. Then

|x -z| 2 < µ(W 1 ) -1 t i=1 µ(W i ) |l -z| 2
for all l ∈ L.

Proof. If x is the closest lattice point in L to z then the claim follows, since the approximation factor given above is always greater than 1. So suppose that a lattice point l ∈ L nearest to z satisfies |l -z| < |x -z|. On the one hand, one clearly has |x -z| 2 ≤ t i=1 µ(W i ). On the other hand, observe that every approximation x = (x 1 , . . . , x t ) found in step (2) satisfies

|x -z| = min{|y -z| | y ∈ L and y 1 = x 1 }, which implies |x -z| = min{|y -z| | y ∈ L and |y 1 -z 1 | 2 ≤ µ(W 1 )}. Hence we must have |l -z| 2 ≥ |l 1 -z 1 | 2 > µ(W 1
). This yields the assertion.

In [START_REF] Turyn | Hadamard matrices, Baumert-Hall units, four-symbol sequences, pulse compression, and surface wave encodings[END_REF], Turyn gave a way of constructing a lattice in dimension nk based upon a polarisation of a lattice in dimension n (where n and k are integers, with k ≥ 2), as follows. The Leech lattice, for instance, can be constructed in this way from a polarisation of E 8 (cf. [START_REF] Griess | Rank 72 high minimum norm lattices[END_REF]Cor. 2.11]), and the extremal even unimodular lattice in dimension 72 found by Nebe (cf. [START_REF] Nebe | An even unimodular 72-lattice with minimum 8[END_REF]) is obtained by a polarisation of the Leech lattice. Definition 1. (cf. [START_REF] Quebbemann | A construction of integral lattices[END_REF]) Let L be a lattice in R n such that √ 2L is even and unimodular. A polarisation of L is a pair of integral sublattices M, N of L such that M + N = L and M ∩ N = 2L. Given such a polarisation and an integer k ≥ 2, one defines M = M(L, M, N, k) by

M := {(u 1 , . . . , u k ) ∈⊥ k i=1 L | u 1 -u i ∈ N (i = 2, . . . , k), u 1 + • • • + u k ∈ M }.
Then M is an integral unimodular lattice, which is even if and only if N is even or k is even. Lemma 4. With L, M, N, n and k as above, we have

M(L, M, N, k) = L(L, N, . . . , N, M ∩ N, ι 1 , . . . , ι k-2 , f ),
where there are k -2 copies of N , ι i : R n0+n(i+1) → R n , (u 0 , . . . , u i+1 ) → u 1 for u j ∈ R n (j ∈ {1, . . . , i + 1}) and i ∈ {1, . . . , k -2}. The map f is defined as follows: Choose a basis (a 1 + b 1 , . . . , a n + b n ) of L = M + N , where a i ∈ N and b i ∈ M for i ∈ {1, . . . , n}. Then let the linear map π N : R n → R n , a i + b i → b i , so in particular π N (l) ∈ N and lπ N (l) ∈ M for every l ∈ L. Now let

f : R n0 ⊥⊥ k-1 i=1 R n → R n , (u 0 , . . . , u k-1 ) → u 1 -π N (2u 1 + u 2 + • • • + u k-1
). Since the proof of this lemma is straightforward verification, we shall omit it here. We now investigate the approximation factor obtained when decoding M with Algorithm A. Example 1 (Algorithm A for the extremal even unimodular lattice Λ 72 in dimension 72 ( [START_REF] Nebe | An even unimodular 72-lattice with minimum 8[END_REF])). This lattice of minimum 8 is obtained from a polarisation of the Leech lattice Λ 24 with k = 3.

Here Algorithm A yields an approximation factor of 9. The two sublattices of Λ 24 yielding Λ 72 are isomorphic to multiples of Λ 24 . Hence according to Remark 1 the maximum number of times that steps (2) and (3) of Algorithm A must be performed to decode a point in R 72 equals sup z∈R 24

|B √

µ(Λ24) (x) ∩ Λ 24 | = 48.

µ(L) := max v∈R n min l∈L |v -l| 2

 2

Conjecture 1 .

 1 If µ(L) ≤ min(L) then the function R n → N, z → |B √ µ(L) (z)∩L| takes its maximum in a deep hole of L.

Proposition 1 .

 1 Let x be the approximation of z found by Algorithm A. Then for all l ∈ L, |z -x| ≤ (4k -3) • |z -l|. Proof. According to Remark 2 and Lemma 4, the approximation factor is at most µ(L) -1 (µ(L) + (k -2)µ(N ) + µ(M ∩ N )). The assertion now follows from µ(N ) ≤ µ(M ∩ N ) = µ(2L) = 4µ(L).


Sanjay Bhattacherjee
email: sanjaybr@isical.ac.in

Palash Sarkar
email: palash@isical.ac.in

An Analysis of the Naor-Naor-Lotspiech Subset Difference Algorithm (For Possibly Incomplete Binary Trees)

Keywords: Broadcast encryption, subset difference, recurrence, expected header length, asymptotic analysis, layered subset difference

The Subset Difference (SD) method is the most popular of Broadcast Encryption schemes due to its use in AACS standard for video discs. The scheme assumes the number of users n to be a power of two. In this paper, we relax this and consider arbitrary values of n. In some applications, this leads to substantial savings in the transmission overhead. Our analysis consists of the following aspects: (1) A recurrence to count N (n, r, h) -the number of revocation patterns for arbitrary values of n and r (number of revoked users) resulting in a header length of h. The recurrence allows us to generate data and hence to completely analyze it for larger n than the brute force method. (2) We do a probabilistic analysis of the subset cover finding algorithm of the SD method and find an expression to evaluate the expected header length E[Xn,r] for arbitrary values of n and r. Using this, E[Xn,r] can be evaluated in O(r log n) time using constant space. (3) While concluding, we suggest a similar method for finding E[Xn,r] for the Layered Subset Difference (LSD) scheme of Halevy and Shamir. (4) In the SD method, for n being a power two, we find asymptotic values of the expected header length.

Introduction

Broadcast Encryption (BE) is a cryptographic method for a center to efficiently broadcast digital contents to a set of users so that only an intended subset of the users (called privileged users) can access the contents. BE has a wide range of applications in the implementation of digital rights management [DRM] such as Internet or mobile video broadcast, pay-TV or even digital media like CD or DVD to name a few. In a BE scenario, the center pre-distributes key decrypting keys to users during initialization. After initialization is complete, when a data message has to be broadcast to the privileged users, it is encrypted using some session key. This session key in turn is encrypted several times using the key encrypting keys for different sets of privileged users. These encryptions of the session key are sent along with the encrypted data as the header. Only privileged users will be able to retrieve the session key (using their own pre-distributed keys) from the header. Using the session key, the actual data that had been broadcast can be retrieved. Even if all the other (revoked) users collude, they should not be able to retrieve the session key.

Broadcast Encryption was introduced in [START_REF] Berkovits | How to broadcast a secret[END_REF] followed by [START_REF] Fiat | Broadcast encryption[END_REF]. Further works on BE were [START_REF] Douglas | On some methods for unconditionally secure key distribution and broadcast encryption[END_REF], [START_REF] Padró | Linear broadcast encryption schemes[END_REF] and [START_REF] Attrapadung | Sequential key derivation patterns for broadcast encryption and key predistribution schemes[END_REF]. Traitor tracing, an important aspect of BE has been studied in [START_REF] Chor | Tracing traitors[END_REF], [START_REF] Naor | Threshold traitor tracing[END_REF], etc. The subset cover framework was introduced in [START_REF] Naor | Revocation and tracing schemes for stateless receivers[END_REF]. The tree-based subset difference method, which is the scheme that we have primarily analyzed in this paper, was also introduced in [START_REF] Naor | Revocation and tracing schemes for stateless receivers[END_REF]. Asymptotic improvements to this scheme were suggested in the LSD scheme of [START_REF] Halevy | The LSD broadcast encryption scheme[END_REF], which is also analyzed as part of our work. The SD method is the most popular BE scheme due to its use in the Advanced Access Content System (AACS) [AAC] standard used for content protection in video-discs. [START_REF] Luby | Combinatorial bounds for broadcast encryption[END_REF] and [START_REF] Padró | Improving the trade-off between storage and communication in broadcast encryption schemes[END_REF] suggest bounds and tradeoffs between different parameters of BE. One of the efficiency parameters is the transmission overhead of a broadcast. It is determined by the header length (the number of encryptions of the session key in the header). Another work on BE is [JHC + 05] in which the worst case header length has been brought down to r.

The SD scheme in [START_REF] Naor | Revocation and tracing schemes for stateless receivers[END_REF] and all the subsequent papers like [START_REF] Park | On the mean number of encryptions for treebased broadcast encryption schemes[END_REF] assume the number of users to be of the form 2 t while, for practical implementations of the scheme, the number of users can be arbitrary. In Section 4.1 of this paper we show that, if we do away with this assumption it will lead to significant saving on the transmission overhead. The following are our main contributions:

1. For the SD scheme, we find a recurrence N (n, r, h) to count the number of revocation patterns for any given arbitrary n and r resulting in a header length of h. Previous to this work, there was no efficient way to generate this count exhaustively for large n other than the brute force method. For the special case when n is a power of two, we derive from it a generating function for the values of N (n, r, h). It is similar to the generating function stated in [START_REF] Park | On the mean number of encryptions for treebased broadcast encryption schemes[END_REF]. 2. For arbitrary n and r, we obtain an expression and hence an algorithm to find the expected header length E[X n,r ] for the SD scheme where X n,r is a random variable taking its values from the set of possible header lengths. The algorithm to evaluate E[X n,r ] takes O(r log n) time using constant space.

Using this algorithm we show that, using the true value of n (instead of rounding it off to a power of two as suggested in the SD scheme) leads to remarkable improvements in the expected header length. 3. Following the same method, we suggest a similar method for computing E[X n,r ] for the Layered Subset Difference (LSD) scheme of [START_REF] Halevy | The LSD broadcast encryption scheme[END_REF]. 4. For n of the form 2 t , we find expressions to perform asymptotic analysis of E[X n,r ]. This explains the empirical observation in [START_REF] Naor | Revocation and tracing schemes for stateless receivers[END_REF] that the expected header length is upper bounded by 1.25r. Our analysis is the first to provide theoretical support to the experimental observations of [START_REF] Naor | Revocation and tracing schemes for stateless receivers[END_REF].

Theorem 10 of [START_REF] Park | On the mean number of encryptions for treebased broadcast encryption schemes[END_REF] gives a method to find E[X n,r ] for n of the power of two. They report their expressions as "complex to compute and hence difficult to get insight from". On the other hand, we see that the complexity of their algorithm is O(r log(nr)) which for r ≤ n 2 is asymptotically same as the complexity of our algorithm (since in practice, r is much smaller than n). Our algorithm is much more appropriate for practical applications where n is arbitrary and it is easily computable. Both these methods use constant space.

The Subset Difference Method

The subset-cover revocation framework proposed in [START_REF] Naor | Revocation and tracing schemes for stateless receivers[END_REF], assumes that a broadcasting system has three parts: (1) an initiation scheme, (2) the broadcast algorithm and (3) the decryption algorithm. Let N be the set of all users and let |N | = n; R is the set of revoked users and let |R| = r. The initiation scheme defines a collection of subsets of users S = {S 1 , S 2 , . . . , S w } where each S j ⊆ N . Each subset S j is assigned a long-lived key L j ; every member u of S j should be able to deduce L j as a part of the decryption algorithm, from the secret information it receives during initiation from the center.

During broadcast, given a revoked set R, the broadcast algorithm is used to partition the remaining users N \R into h disjoint subsets S i1 , S i2 , . . . , S i h so that

N \ R = h k=1 S i k . This sub-collection of disjoint subsets is called the cover S c for N \ R (S c = {S i1 , S i2 , . . . , S i h }).
A uniform random session key K is used to encrypt the broadcast message M by some symmetric key encryption algorithm. K is then encrypted h times with L i1 , L i2 , . . . , L i h and sent as the header with encrypted M . A privileged user, upon receiving the above broadcast, uses the decryption algorithm to deduce some L j using its own secret information, and hence decrypt the encrypted session key K. This session key will further be used to decrypt the broadcast data.

For the Subset Difference method, the Subset-Cover Revocation Framework is specified as follows: In the initiation scheme that defines the collection S SD of subsets, the users in N are viewed as the leaves of a complete binary tree T 0 rooted at node 0. All internal nodes in T 0 are numbered on a top-to-bottom (level-wise) and then left-to-right (at each level) basis. Hence every internal node i (root of subtree T i ) represents a group of users that are leaves of T i . For each internal node i and a successor node j of i in T 0 , a subset S i,j is included into the collection S SD of subsets. Such a subset S i,j has every user that is a successor of the node i but is not a successor of node j (those leaves which are in the subtree T i but not in T j ). In other words, S i,j corresponds to the users in T i \ T j . A subset corresponding to all users (represented by the full binary tree T 0 ) is added to S SD .

During broadcast, the center starts with the set R of revoked users. To find the cover S c , the center first finds the Steiner tree ST (R) i.e.; the minimal subtree of the full binary tree T 0 , all of whose leaves are in R. T ′ , a copy of ST (R) is created and the following algorithm is applied to find the cover S c : 1. Find leaf nodes i and j of T ′ such that the subtree rooted at the leastcommon-ancestor v of these two nodes does not contain any other leaf of T ′ . 2. Let l and k be the two children of v such that i is a descendant of (or the same node as) l and j is a descendant of (or the same node as) k. If l = i, add the subset S l,i to the cover S c . Similarly, if k = j, add the subset S k,j to the cover S c . 3. Delete the subtree rooted at v in T ′ . Hence v becomes a leaf node in T ′ . 4. Repeat the above three steps iteratively until there is only one leaf remaining.

For the last leaf node z, add the set S 0,z to the cover S c .

The cardinality of S c is called the header length and determines the transmission overhead.

Note 1. The original algorithm in [START_REF] Naor | Revocation and tracing schemes for stateless receivers[END_REF] and all subsequent analysis [START_REF] Park | On the mean number of encryptions for treebased broadcast encryption schemes[END_REF] [AK08] [MMW09] consider n to be a power of two. In contrast, we work with arbitrary n.

Later, we argue that this can lead to substantial reduction in the transmission overhead.

Counting Revocation Patterns

A fixed permutation of the users where some are revoked and others are privileged is called a revocation pattern. The algorithm to find the subset cover takes as an input a revocation pattern and outputs the subset cover. The number of subsets h in the subset cover is called the header length.

N (n, r, h) is defined as the number of revocation patterns with r revoked users (out of total n users) that are covered by a header of length exactly h.

T (n, r, h) is defined as the number of revocation patterns with r revoked users (out of total n users) that are covered by a header of length h such that there is at least one revoked user in each of the two subtrees of the root node.

For an arbitrary n (2 t0 < n ≤ 2 t0+1 for some t 0 ), T (n, r, h) and N (n, r, h) are given by the following recurrences:

T (n, r, h) = r-1 r1=1 h h1=0 N (2 t0 , r 1 , h 1 ) × N (n -2 t0 , r -r 1 , h -h 1 )
(1)

N (n, r, h) = T (n, r, h) + t0 ℓ=1 q ℓ × T (2 ℓ , r, h -1) + t0 ℓ=1 ρ ℓ -1 2 ℓ-1 × T (ρ ℓ , r, h -1) (2)
where q ℓ = n 2 ℓ and ρ ℓ = n -(q ℓ × 2 ℓ ). The base cases to the recurrences T (n, r, h) and N (n, r, h) are as follows:

T (n, r, h) r < 0 r = 0 r = 1 2 ≤ r < n r = n r > n h < 0 0 0 0 0 0 0 h = 0 0 0 0 0 1 0 h ≥ 1 0 0 0 from (1) 0 0 N (n, r, h) r < 0 r = 0 r = 1 2 ≤ r < n r = n r > n h < 0 0 0 0 0 0 0 h = 0 0 0 0 0 1 0 h = 1 0 1 n from (2) 0 0 h > 1 0 0 0 from (2) 0 0 (3)
A dynamic programming based algorithm to count N (n, r, h) follows from the recurrence relations (1) and (2). We omit the description of this algorithm and the proof of correctness of the recurrence relations due to space constraints. For a given n i , r i and h i , after the smaller values have been computed, the computation complexity of N (n i , r i , h i ) and T (n i , r i , h i ) are O(log n) and O(rh) respectively. Hence, the overall complexity is O(n log nrh+nr 2 h 2 ). This algorithm will require O(nrh) space. This is a significant improvement over the brute force method which involves enumeration of the n r revocation patterns, and hence cannot be used for large values of n and r. Moreover, if the complete data for all r and h is needed for a given n, the subset cover finding algorithm has to be run for all the 2 n revocation patterns. The following table contains results of running the dynamic programming based algorithm for some values of n, r and h. n r h N (n, r, h) n r h N (n, r, h) 100 49 30 1.37 × 10 28 115 50 36 1.12 × 10 32 110 49 38 1.06 × 10 30 117 60 37 1.00 × 10 33 (4) From Recurrences (1) and (2), we find the generating function for the sequence N (n, r, h) when the number of users is n = 2 m . We omit the proof here due to lack of space.

Theorem 1 The generating function for the sequence N m (r, h) of numbers is given by X m (x, y) where

X m (x, y) = X m-1 (x, y) -xy 2 m-1 2 + xy 2 m + 2 m x 2 y 2 m -1 + m-1 i=1 2 m-i xy 2 m -2 i × X i-1 (x, y) -xy 2 i-1 2 . ( 5
)
A similar generating function was found by Park and Blake in [START_REF] Park | On the mean number of encryptions for treebased broadcast encryption schemes[END_REF]. It was derived based on the structural properties of the tree T 0 used in creating the subsets of the subset difference method. We have taken a different approach of first finding the recurrence relations for the sequence N (n, r, h) and then have derived the generating function from it. Our generating function is of a slightly different form but gives rise to the same sequence.

Expected Header Length For Any n And r

For an arbitrary number of users n, and a fixed r, we find the expected header length. This is done by finding the probability that a node in T 0 contributes a set to the subset cover (and hence the header). Summing up the probabilities for each node in the tree, we evaluate the expected header length. We consider the random experiment where r out of the n initially un-revoked leaves of the tree T 0 are chosen one-by-one uniformly at random without replacement and revoked. This gives rise to a revocation pattern and hence a corresponding subset cover S c and its header length h. Let X n,r be the random variable taking the value of the header length (cover size). Let X t n,r ∈ {0, 1} be a random variable associated with node t of T 0 . X t n,r = 1 denotes the event that the cover contains a subset of the form T t \ T t ′ where t ′ is some node in the subtree T t . Similarly, X t n,r = 0 denotes the event that there is no subset in the cover of the form T t \ T t ′ . If node t is the k th node of level ℓ of T 0 , then X t n,r will also be written as X ℓ,k n,r . There are n -1 internal nodes in T 0 . Then for a revocation pattern, we can write: X n,r = X 0 n,r + X 1 n,r + . . . + X n-2 n,r . By linearity of expectation, we can write:

E[X n,r ] = E[X 0 n,r ] + E[X 1 n,r ] + . . . + E[X n-2 n,r ]. (6)
Since all the random variables X t n,r follow Bernoulli distribution with probability Pr[X t n,r = 1], we get:

E[X n,r ] = Pr[X 0 n,r = 1] + Pr[X 1 n,r = 1] + . . . + Pr[X n-2 n,r = 1]. ( 7
)
So the problem boils down to finding Pr[X t n,r = 1] for a given internal node t. Here, we define η r (i, j) as the probability of choosing r elements from a set of i elements such that some fixed j elements are not chosen. So, if j ≥ ir + 1, then η r (i, j) = 0 and for 0 < j < ir + 1,

η r (i, j) = 1 - j i 1 - j i -1 1 - j i -2 . . . 1 - j i -r + 1 = (i -j) r (i) r . ( 8
)
For an internal node t (the k th node of level ℓ), let p be the predecessor and let s be the other child node of p (the sibling of node t). For a subset of the form T t \ T t ′ to occur in the cover (where t ′ is some node in the subtree T t ), there should be at least one revoked user in exactly one of the subtrees of the node t while there should be no revoked user in the other subtree of t. The subtree rooted at s should also have at least one revoked user. Let R ℓ,k lef t (R ℓ,k right ) be the random variable taking up values to indicate the number of revoked users in the left (right) subtree of T t . Also, let R ℓ,k sibling be the random variable taking up values to indicate the number of revoked users in T s . Then we have the following lemma:

Lemma 2 When r > 0, the probability that the cover S c contains a set of the form T t \ T t ′ is given by Pr

[X ℓ,k n,r = 1] where Pr[X ℓ,k n,r = 1] = Pr[R ℓ,k sibling > 0 ∧ R ℓ,k right > 0 ∧ R ℓ,k lef t = 0] + Pr[R ℓ,k sibling > 0 ∧ R ℓ,k lef t > 0 ∧ R ℓ,k right = 0]. (9)
Let A be the event R ℓ,k sibling > 0. Similarly, let B and C be the events R ℓ,k right > 0 and R ℓ,k lef t > 0 respectively. Then,

Pr[X ℓ,k n,r = 1] = Pr[A ∧ B ∧ C] + Pr[A ∧ B ∧ C]. For the moment, assume Pr[C] > 0 and Pr[B ∧ C] > 0. Then, Pr[A ∧ B ∧ C] = (1 -Pr[A ∨ B|C]) × Pr[C] = Pr[C] -Pr[A ∧ C] -Pr[B ∧ C] + Pr[A ∧ B ∧ C]. (10)
It can be verified that (10) holds even if Pr

[C] = 0. Similarly, Pr[A ∧ B ∧ C] = Pr[B] -Pr[A ∧ B] -Pr[B ∧ C] + Pr[A ∧ B ∧ C]. Hence, Pr[X ℓ,k n,r = 1] = Pr[B] + Pr[C] -Pr[A ∧ B] -Pr[A ∧ C] -2 Pr[B ∧ C] + 2 Pr[A ∧ B ∧ C] (11)
As a result, we get the following theorem:

Theorem 3 Let n ℓ and n r be the number of leaf nodes in the left and right subtrees respectively of the k th node of level ℓ and let n s be the number of leaf nodes in its sibling subtree T s . Then,

Pr[X ℓ,k n,r = 1] = η r (n, n ℓ ) + η r (n, n r ) -η r (n, n s + n ℓ ) -η r (n, n s + n r ) -2η r (n, n ℓ + n r ) + 2η r (n, n s + n ℓ + n r ) (12)
Equation ( 7) can be rewritten as follows:

E[X n,r ] = t0+1 ℓ=1 q ℓ k=1 Pr[X ℓ,k n,r = 1] + t0 ℓ=1 ρ ℓ -1 2 ℓ-1 × Pr[X ℓ,q ℓ +1 n,r = 1]. (13)
Here, level t 0 + 1 has only one node (the root node) for which Pr[X 0 n,r = 1] = η r (n, 2 t0 ) + η r (n, n -2 t0 ) which is a special case of (12). Computing Pr[X ℓ,k n,r = 1] requires evaluating the η function which requires r multiplications. At level ℓ, Pr[X ℓ,k n,r = 1] is same for k = 1, . . . , q ℓ -1 and needs to be computed once. Hence, for these q ℓ -1 nodes for all the ℓ levels O(r log n) multiplications are required. Contribution from the q th ℓ and (q ℓ + 1) th nodes at the level ℓ can be computed using O(r log n) multiplications and so the overall complexity is O(r log n) multiplications. The space complexity is O(1). By running this algorithm, we make an interesting observation that for r = 2, n = (2 20 -1) and 2 20 , as n increases from 2 20 -1, 2 20 to 2 20 + 1. This also happens for other similar values of n.

Power-of-two Anomaly

The SD scheme of [START_REF] Naor | Revocation and tracing schemes for stateless receivers[END_REF] and all subsequent work on it, assume n to be a power of 2. For most practical implementations, n will not be a power of 2. Hence, to be able to use the scheme, additional dummy users have to be assumed and added to the collection of users to make n a power of 2. If n is of the form 2 t0 + 1, then the next high power is 2 t0+1 and hence the number of dummy users added is almost equal to n. These dummy users can either be assumed to be revoked or privileged. Unless the implementation requires redundancy in the number of privileged users, assuming the dummy users to be privileged will lead to useless increase in key storage and may lead to increase in header length. This may be less of a problem for implementations in DVD-s, but it will definitely be a serious issue with implementations like pay-TV where user storage as well as transmission overhead are crucial efficiency parameters. The storage space required by each user is 1 2 log 2 n + 1 2 log n + 1 in the SD method. If the number of dummy users is almost equal to n, then the useless storage is around log 2 log n + 1 2 log 2 2 + 1 2 log 2 which is significant compared to the total storage size of the user. Hence, it is more reasonable to assume the dummy users to be revoked. But such an assumption adversely affects the efficiency of the scheme. The following table enlists the true values of n and r, the corresponding assumed values of n ′ (of the form 2 t0+1 ) and r ′ and their respective expected header lengths. The above table shows that if n is rounded off to n ′ (a power of 2) as suggested by [START_REF] Naor | Revocation and tracing schemes for stateless receivers[END_REF] and all subsequent work, the expected header length suffers an enormous increase. This clearly brings out the significance of our contribution.

n r E[X n,r ] n ′ r ′ E[X n ′ ,

Complete Tree: Asymptotic Analysis of Expected Header Length

For n = 2 t0+1 , n ℓ = n r and hence for a node t (the k th node of level ℓ), (12) can be written as:

Pr[X ℓ,k n,r = 1] = 2 η r (n, 2 ℓ-1 ) -η r (n, 2 ℓ ) -η r (n, 3 × 2 ℓ-1 ) + η r (n, 2 ℓ+1 ) . ( 15
)
This probability is independent of k and hence, is equal for all nodes at level ℓ which we denote by B (ℓ) n,r . We define the expected header length H n,r as:

H n,r = E[X n,r ] = t0+1 ℓ=1 2 t0+1-ℓ B (ℓ) n,r . We define D n,r = H n,r -H n,r-1 so that H n,r = H n,r-1 + D n,r = 1 + r i=2 D n,i . Expanding the expressions for B (ℓ)
n,r+1 and B (ℓ) n,r , and simplifying, we obtain the following:

D n,r+1 = n n -r [-η r (n, 1) + η r (n, 2) + 3η r (n, 3)] - 3n n -r t0 ℓ=1 η r (n, 2 × 2 ℓ -η r (n, 3 × 2 ℓ ) . (16)
For the asymptotic analysis, we define H r = lim n→∞ H n,r , D r = lim n→∞ D n,r and so, H r = 1 + r i=2 D i . Using algebraic manipulations, we get the following result: The above table lists the values of D r and Hr r for small values of r. This table shows the ratio Hr r is 1.25 for r = 2 and decreases with increasing r. This explains the empirical observation in [START_REF] Naor | Revocation and tracing schemes for stateless receivers[END_REF] that the expected header length is 1.25r.

Theorem 4 D r+1 ↑ 3 -3K r where K r = -1 2 r + r j=1 (-1) j r j (2 j -3 j ) (2 j -1) .

Analysis of the Layered Subset Difference Scheme

The basic LSD Scheme of [START_REF] Halevy | The LSD broadcast encryption scheme[END_REF] causes an asymptotic improvement in the number of keys stored per user over the SD scheme of [START_REF] Naor | Revocation and tracing schemes for stateless receivers[END_REF], with a compromise on the header length. The amount of information that a user has to store in the SD method, improves from O(log 2 (n)) to O(log 3/2 (n)). It modifies the SD scheme by dividing the levels of nodes of the tree T 0 into √ log n layers with each layer containing √ log n levels of T 0 . A level at the border of two adjacent layers is said to be special and is included in both the layers (above and below it). To get the collection of subsets S LSD for the LSD scheme, a subset S i,j in the collection S SD of the SD method is divided into two subsets S i,k and S k,j where node k is either in the same layer as node i or is at a special level.

For a node t, let ℓ t denote the level of t and k t be its index in that level. Let NSDesc(t) be the set of all non-special descendant nodes of node t which are not at the same layer as t. Similar to the technique used for the SD method in Section 4, finding the expected header length for LSD boils down to finding Pr[X ℓi,ki n,r = 1 ∧ X ℓj ,kj n,r

= 1] for a pair of nodes (i, j) such that j is a descendant node of i in T 0 and j ∈ NSDesc(i). The event X ℓi,ki n,r = 1 ∧ X ℓj ,kj n,r = 1 occurs when there is at least one revoked user in each of the following subtrees: the subtree rooted at the sibling node of i and each of the two child subtrees of j. Using this characterization, we find the expected header length.

  499. So, there is a sharp change in the value of E[Xn,r] r

  r ′ ] 2 16 + 1 2 7 160.03 2 17 2 7 + (2 16 -1) 38065.75 2 16 + 8 2 7 160.01 2 17 2 7 + (2 16 -8) 38066.14 2 16 + 2 15 2 7 159.15 2 17 2 7 + (2 15 ) 29771.38 2 16 + 1 2 10 1253.96 2 17 2 10 + (2 16 -1) 38008.61 2 16 + 8 2 10 1253.85 2 17 2 10 + (2 16 -8) 38009.11 2 16 + 2 15 2 10 1260.33 2 17 2 10 + (2 15 ) 30275.03

	(14)