P Gaudry

AND F Hess

N P Smart

CONSTRUCTIVE AND DESTRUCTIVE FACETS OF WEIL DESCENT ON ELLIPTIC CURVES

In this paper we look in detail at the curves which arise in the method of Galbraith and Smart for producing curves in the Weil restriction of an elliptic curve over a nite eld of characteristic two of composite degree. We explain how this method can be used to construct hyperelliptic cryptosystems which could be as secure as cryptosystems based on the original elliptic curve. On the other hand, we show that the same technique may provide a way of attacking the original elliptic curve cryptosystem using recent advances in the study of the discrete logarithm problem on hyperelliptic curves.

We examine the resulting higher genus curves in some detail and propose an additional check on elliptic curve systems de ned over elds of characteristic two so as to make them immune from the methods in this paper.

Introduction

In this paper we address two problems: how to construct hyperelliptic cryptosystems and how to attack elliptic curve cryptosystems de ned over elds of composite degree over F 2 .

As explained in 17], there is currently no practical method which generates cryptographically secure Jacobians of hyperelliptic curves that have no special added structure. We shall present a method that will produce a hyperelliptic Jacobian related to a `random' elliptic curve, which is secure assuming one believes the discrete logarithm problem on the elliptic curve is itself hard.

For the second problem we turn our construction of hyperelliptic cryptosystems on its head and argue that this provides evidence for the weakness of the original elliptic curve discrete logarithm problem. We stress that this does not provide evidence for the weakness of elliptic curve systems in general, but only those which are de ned over the special nite elds considered in this paper. These elds are extensions of composite degree over the eld F 2 . Let E : Y 2 + XY = X 3 + X 2 + denote an elliptic curve de ned over a eld of characteristic two, which is not de ned over a proper sub eld of K = F q n . We let m denote an integer, which is de ned in Lemma 6, that satis es 1 m n. We assume that our elliptic curve satis es one of the following conditions; or Tr K=F2 ( ) = 0:

1991 Mathematics Subject Classi cation. Primary: 94A60, 11T71, Secondary: 11Y99, 14H52, 14Q15.

Key words and phrases. function elds, divisor class group, cryptography, elliptic curves. 1

We shall see that if n is even, then only approximately 1=(2q) of all elliptic curves over K are eliminated by the above condition. We shall prove the following Theorem 1. Let E(F q n ) denote an elliptic curve satsifying condition (y). Let #E(F q n ) = ph, where p is a large prime. Assuming the map de ned below does not have kernel divisible by p, one can solve the discrete logarithm problem in the p-cyclic subgroup of E(F q n ) in time O(q 2+ ) where the complexity estimate holds for a xed value of n 4 as q ! 1.

The complexity in the Theorem should be compared to the time estimate of O(q n=2 ) for the best general purpose algorithm, namely Pollard's rho method. We conjecture that the condition on the kernel of the map hold in all cryptographically interesting cases.

The implied constant in the O( ) notation of the Theorem contains a very bad dependence on n, of the order of O(2 n !). Hence, for certain values of n the crossover point between the method of the Theorem and Pollard's rho method may be at higher values of q than are used in practical elliptic curve cryptosystems. However, we shall exhibit experimental evidence that for n = 4 and around 1=q of the elliptic curves de ned over F q 4 , the method of the above Theorem is better than Pollard rho for values of q used in practice. For other elliptic curves over F q 4 our method is only asymptotically better than Pollard rho, and further practical experiments need to be carried out to deduce whether the crossover point is at a size of q which is of cryptographic interest.

Our methods are based on the idea of Weil descent on elliptic curves. Hence, much of the following is an extension of the work begun by Frey in 7] and continued in 9], to which we refer the reader for further details. The details of elliptic curve cryptosystems which we shall require can be found in 3].

The paper is organized as follows. In Section 2 we give some simple examples of curves de ned over a special type of eld extension, for which hand calculation is particularly simple. In Section 3 we give proofs that the properties observed in the hand calculations hold in general. In addition, we shall construct an explicit group homomorphism : E(F q n ) ! Cl 0 (H); where Cl 0 (H) is the degree zero divisor class group of a hyperelliptic function eld over F q . As we stated earlier, if the map maps the cryptographically interesting subgroup of E(F q n ) to the zero element in Cl 0 (H) then our method will fail to work. However, since it is highly unlikely that the kernel of will contain almost the whole of the group E(F q n ), we expect that our method will work in all cryptographically interesting examples.

In Section 4 we show how our method of producing curves in the Weil restriction can be used to construct hyperelliptic cryptosystems, whilst in Section 5 we explain how one could possibly attack the underlying elliptic curve system using the Weil restriction. In Section 6 we report on an experiment using the index calculus algorithm of Gaudry on one of the curves of genus four produced by our method; this is used to help decide which genera should be used in practice for constructing cryptographic systems and which elliptic curve systems are made weaker by our methods. Finally in Section 7, we turn our attention to other types of nite elds and discuss why the ideas of this paper are unlikely to work in other cases. In particular, for a large proportion of elliptic curves de ned over F 2 p , where p is prime, we show that the methods of this paper give no decrease in security of the resulting cryptosystem.

The rst author would like to thank R. Harley for many fruitful discussions on the hyperelliptic discrete log; some tricks are due to him. The second author would like to thank J. Cannon for his support while this work was in preparation. The third author would like to thank G. Frey, S. Galbraith, E. Scheafer and S. Vanstone, for various discussions whilst the work on this paper was carried out. All three authors would like to thank S. Galbraith, N. Koblitz and K. Paterson and an anonymous referee, who read and commented on earlier drafts of this paper. The calculations in this paper were made possible by using a variety of packages including Magma, KASH, LiDIA, PARI/GP and ZEN.

Example Curves in the Weil Restriction

Let k = F q denote some nite eld of characteristic two, and let n 2 denote an integer. In practice we are thinking of the situation where n is quite small and q is large enough so that q n > 2 160 . Let K denote the eld extension F q n , with k-basis f 0 ; 1 ; : : : ; n 1 g.

In this section we shall consider elliptic curves E over K, given by the equation:

Y 2 + XY = X 3 + ;

where 2 K. Notice that for such curves condition (y) is satis ed. We assume E(F q n ) contains a subgroup of prime order p with p q n . We set = b 0 0 + b 1 1 + : : : + b n 1 n 1 ; X = x 0 0 + x 1 1 + : : : + x n 1 n 1 ; Y = y 0 0 + y 1 1 + : : : + y n 1 n 1 ; where b i 2 k are given and x i ; y i 2 k are variables. Substituting these equations into the equation for our elliptic curve, and equating coe cients of i , we obtain an abelian variety A de ned over k, of dimension n, the group law on A being given by the group law on E(K). The variety A is called the Weil restriction, and the above process is called Weil descent.

Since A is isomorphic to E(K) as a group, the variety A will contain an irreducible subvariety B (we do not exclude B = A) with group order divisible by p. In curves of cryptographic interest, where p q n , this subvariety will either equal the whole of A or have dimension at least n 1, which can be seen by simple cardinality arguments. The variety B is the part of A in which our discrete logarithm problem is de ned. We wish to nd a curve C in A whose Jacobian contains a subvariety isogenous to B. Recall that B is the part of A which is interesting for cryptographic applications. Hence, we must have g = dim Jac(C) dim B where dim B as stated above will be either n or n 1. For the applications we would like the genus of C to be linear in n, but it is highly unlikely such a curve exists at all.

For the rest of this section we shall look at a special set of nite elds for which it is relatively easy to perform calculations. Our aim is to x the ideas and provide a rich set of examples for the reader and for later in the paper. In the next section we shall show that the remarkable properties we observe in this section hold in general for elds of characteristic two. The method used is a natural extension of the one presented in 9].

We specialize to those elds K for which we can take i = 2 i in our basis of K over k where + 2 + 4 + + 2 n 1 = 1. The reason for choosing such a basis is so that the curves in the Weil restriction below have `small' degree and are easy to write down. One reason for this is that squaring an element represented by such a basis is simply a cyclic shift of the coe cients since 2 n = 2 n 1 2 = 1 + + 2 + + 2 n 2 2 = 1 + 2 + 4 + + 2 n 1 = :

However, such a basis does not always exist, since we require the existence of an irreducible factor of degree n of the polynomial h(x) = x 2 n 1 + + x 4 + x 2 + x+1 over the eld k. Hence, we clearly require that the degree of k over F 2 must be coprime to n, which we assume to be the case for the rest of this section. In addition, for a root of such an irreducible factor we require that the set f ; 2 ; 4 ; : : : ; 2 n 1 g forms a basis of K over k. Hence, for this section, we have restricted the choice of q and n. For n = 2, we can always use the element de ned by 2 + +1 = 0 whilst for n = 3 we can always use the element de ned by 3 + 2 + 1 = 0. For higher values of n we can obtain many irreducible factors of h(x) of degree n over F 2 , and by the coprimality of the degree of k to n we see that such factors will be irreducible over k. For example, if n + 1 is a prime and q is a generator of the multiplicative group of the eld F n+1 then we can take as a generator of K over k, where n + n 1 + + + 1 = 0.

To produce a curve of low genus in A one could produce a curve of low degree, and hence of hopefully low genus. Such a curve of low degree can be obtained by intersecting A with the hyperplanes given by x 0 = x 1 = = x n 1 = x. Hence, we look at the subvariety de ned by restricting X to lie in k. We obtain a curve C de ned by the equations C :

8 > > > < > > > :
y 2 n 1 + xy 0 + x 3 + b 0 = 0; y 2 0 + xy 1 + x 3 + b 1 = 0;

. . . y 2 n 2 + xy n 1 + x 3 + b n 1 = 0: That we can obtain such sparse equations is due to our choice of basis of K over k. On elimination of variables we produce a curve in x and y = y 0 of the form

C : y 2 n + x 2 n 1 y + n 1 X i=0 x 2 n +2 i + g(x)
where g(x) is a polynomial, depending on b 0 ; : : : ; b n 1 , of degree less than or equal to 2 n . The polynomial g(x) is given by the formulae:

g(x) = n X i=1 b 2 n i i x 2 n 2 n i+1
; where we make the identi cation b n = b 0 . The Jacobians of the irreducible components of the curve C are isogenous to abelian varieties which contain subvarieties of A, by the arguments of Section 2 of 9]. In examples of cryptographic interest the subvariety B of A has order divisible by a large prime p, hence the degree of the isogeny is likely to be coprime to p. Therefore, we can expect that the Jacobians actually contain a subgroup isomorphic to the subgroup of B of order p.

We give the following examples: n = 2.

C 2 : y 4 + x 3 y + x 6 + x 5 + b 0 x 2 + b 2 1 = 0: If the original elliptic curve is de ned over the base eld, i.e. b 0 = b 1 , then the curve C has two irreducible components, each being an elliptic curve. In all other cases it is irreducible. Substituting a large number of elements for the parameters b 0 and b 1 into the equation for C 2 , we found that experimentally the genus of this curve always seems to be 2. n = 3.

C 3 : y 8 + x 7 y + x 12 + x 10 + x 9 + b 0 x 6 + b 2 2 x 4 + b 4 1 = 0: The curve is reducible when b 0 = b 1 = b 2 , in other words when the original elliptic curve is de ned over the base eld k. In all other cases it is irreducible, and experimentally the genus of this curve always seems to be 3 or 4. n = 4.

C 4 : y 16 + x 15 y + x 24 + x 20 + x 18 + x 17 + b 0 x 14 + b 2 3 x 12 + b 4 2 x 8 + b 8 1 = 0:

Experimentally, when the curve is irreducible, the genus of this curve always seems to be at most 8. This curve is reducible when b 3 = b 0 + b 1 + b 2 , and when it is reducible, one of the components is given by C 4a : y 8 + x 4 y 4 + x 6 y 2 + x 7 y + x 12 + x 9 + b 0 x 6 + (b 2 2 + b 2 1 )x 4 + b 4 1 = 0: When C 4a is irreducible it experimentally always has genus at most 4.

Note, in all the cases when the curve C was irreducible, it experimentally had genus equal to 2 n 1 or 2 n 1 1. In addition, we noticed that the irreducible components were always hyperelliptic. In the next section we shall prove that these remarkable properties hold in general for curves satisfying condition (y).

Hyperellipticity and Genus of Curves in the Weil Restriction

In this section we show that the observations of the previous section about the genus, irreducibility and hyperellipticity of the curves C hold in general. In addition, we shall show the existence of a computable mapping from E(F q n ) to the divisor class group of a hyperelliptic curve. It is this mapping which translates the hard elliptic curve discrete logarithm problem into a potentially easier hyperelliptic discrete logarithm problem.

3.1. The curve in the Weil restriction. We shall now let K denote an arbitrary degree n extension of a nite eld k of characteristic two of q elements. We shall make no assumptions about the existence of special types of bases of K over k as we did in the previous section. In this section, to keep track of which elds we are considering, all xed elements of K will be denoted by Greek letters.

We take an elliptic curve E : Y 2 + XY = X 3 + X 2 + ; where ; 2 K, 6 = 0. We do not assume condition (y) unless explicitly stated.

We can form the Weil restriction as in the previous section by substituting the coordinate representations of X and Y and expanding with respect to any given basis of K over k, but for simplicity we assume that the sum of the basis elements is one. We intersect the resulting abelian variety A with the hyperplanes which mark out the subvariety of values of X which lie in k. The resulting subvariety of A will be a curve de ned over k, in n + 1 dimensional space, which we shall denote by C, as in the previous section.

We wish to study the curves C geometrically, so we consider C over the algebraic closure of k. In fact, we shall only need to go to the extension K.

Lemma 2. By a linear change of variables y i 7 ! w i , de ned over K, we nd that C is birationally equivalent to the curve D, de ned over K, given by D :

8 > < > :
w 2 0 + xw 0 + x 3 + 0 x 2 + 0 = 0;

. . .

w 2 n 1 + xw n 1 + x 3 + n 1 x 2 + n 1 = 0;
where we have j = j ( ) and j = j ( ), with the Frobenius automorphism of K over k.

We can extend the Frobenius automorphism to K x; w 0 ; : : : ; w n 1 ] via (x) = x, (w i ) = w i+1 for 0 i < n 1 and (w n 1 ) = w 0 . We obtain (y i ) = y i for all 0 i n 1.

Proof. It is convenient to prove the Frobenius automorphism statement rst. That can be extended as stated is obvious. Next set T = j ( i ) 0 i;j n 1 2 K n n and notice that T is invertible since TT t = Tr K=k ( i j ) is invertible because nite eld extensions are separable. The linear change of variables of the Lemma is then (w 0 ; : : : ; w n 1 ) = (y 0 ; : : : ; y n 1 ) T.

Let t i denote the i-th column of T, for 0 i n 1. The y i are expressed as K-linear combinations of the w i via (y 0 ; : : : ; y n 1 ) = (w 0 ; : : : ; w n 1 ) T 1 . We apply to (w 0 ; : : : ; w n 1 ) = (y 0 ; : : : ; y n 1 ) T and obtain (w 1 ; : : : ; w n 1 ; w 0 ) = ( (y 0 ); : : : ; (y n 1 )) t 1 ; : : : ; t n 1 ; t 0 = (y 0 ; : : : ; y n 1 ) t 1 ; : : : ; t n 1 ; t 0 : The second equation holds because of the relation of the y i and w i . As the matrix t 1 ; : : : ; t n 1 ; t 0 is invertible we conclude (y i ) = y i . We are left to prove the birational equivalence of C and D. Let 0 ; : : : ; n 1 be a basis of K over k with P i = 1. The equations of C are obtained by expanding Y = X y i i ; = X a i i = X b i i and X = x in E, and equating the resulting coe cients of the i . We obtain f i 2 k x; y 0 ; : : : ; y n 1 ] such that w 2 0 + xw 0 + x 3 + 0 x 2 + 0 = n 1 X i=0 f i (x; y 0 ; : : : ; y n 1 ) i ; :

The corresponding equations for C are C :

8 > < > :
f 0 (x; y 0 ; : : : ; y n 1 ) = 0;

. . . f n 1 (x; y 0 ; : : : ; y n 1 ) = 0:

We denote the left hand sides of D by g i 2 K x; w 0 ; : : : ; w n 1 ]. Upon applying T columnwise to the equations of C we then see f i (x; y 0 ; : : : ; y n 1 ) 0 i n 1 T = X i f i (x; y 0 ; : : : ; y n 1 ) j ( i ) 0 j n 1 = j X i f i (x; y 0 ; : : : ; y n 1 ) i 0 j n 1 = j w 2 0 + xw 0 + x 3 + 0 x 2 + 0 0 j n 1 = g i (x; w 0 ; : : : ; w n 1 ) 0 i n 1 ; which shows that C is linearly transformed into D by T.

Let F i be the splitting eld of the i-th equation de ning D over K(x).

Lemma 3. We can form the compositum F = F 0 F n 1 over K(x) without ambiguity. Let m 2 Z such that F : K(x)] = 2 m . Viewed over K the curve D has 2 n m irreducible reduced components, each having function eld K-isomorphic to F. Proof. We can form F without ambiguity because the extensions F i =K(x) are all quadratic, hence Galois over K(x). More speci cially, in order to generate F over K(x) we can choose a suitable subset of m equations of the equations de ning the curve D, such that adjoining w li , for 1 i m, to K(x) gives F, with w li a root of the left hand side of the i-th such equation. The remaining n m equations of D will each have two solutions w vj and w vj + x in F.

Consider the homomorphism : K x; w 0 ; : : : ; w n 1 ] ! K x; w 0 ; : : : ; w n 1 ] F:

The kernel I of this homomorphism is a prime ideal of dimension one since F is a eld of transcendence degree one over K being generated by x; w 0 ; : : : ; w n 1 over K. This prime ideal contains the left hand sides of D by construction of F. Therefore, I de nes an irreducible reduced component of D having function eld K-isomorphic to F.

The statement about the number of these components follows from the possible choices of w vj or w vj + x in the de nition of the homomorphism. This can be seen in detail as follows: Assume I were contained in the kernel J of a homomorphism as above which maps w vj to w vj + x. There are f; g 2 K x; w 0 ; : : : ; w m 1 ] such that (g); (g) 6 = 0 and w vj = (f)= (g) = (f)= (g). Then gw vj + f 2 I J and g(w vj + x) + f 2 J hence gx 2 J and x 2 J because (g) 6 = 0 and J is prime. This is clearly a contradiction as x is not mapped to zero by .

3.2. Artin-Schreier properties. If we multiply the equations de ning D by x 2 , substitute s i = w i =x+ 1=2 i =x and z = 1=x, we see that another model for our curve

D is F : 8 > > < > > : s 2 0 + s 0 + z 1 + 0 + 1=2 0 z = 0; . . . s 2 n 1 + s n 1 + z 1 + n 1 + 1=2 n 1 z = 0:
The advantage of this model is that we can apply Artin-Schreier theory as outlined in 2, pp. 22{24], 14, pp. 275{281] and 18, p. 115]. We will use the following special version of 14, p. 279, Thm 3.3]: Theorem 4. Let p be a prime number, }(x) = x p x be the Artin-Schreier operator, K be a eld of characteristic p and K be a xed separable closure of K. For every additive subgroup K + with }(K) K there is a eld L = K } 1 ( ) with K L K obtained by adjoining all roots of all polynomials x p x d for d 2 in K to K. Given this, the map 7 ! L = K } 1 ( ) de nes a 1-1 correspondence between such additive subgroups and Abelian extensions L=K in K of exponent p.

Before giving the result we state the following Lemma which will be used repeatedly in the sequel. Lemma 5. Any sum of an even number of the j is of the form v 2 + v with a suitable v 2 F 2 ( ).

Proof. For f(t) = P i d i t i 2 F 2 t] we de ne f(t)" = P i d i " 2 i for all " 2 K, thereby turning the additive group K + of K into an F 2 t]-module. The required statement is then reformulated as follows: For f(t) 2 F 2 t] with f(1) = 0 there is a suitable v 2 F 2 ( ) such that f(t) = (t + 1)v. But this is now easily seen to be true.

Namely, f(t) is divisible by t + 1 and v can thus be chosen to be f(t)=(t + 1) .

Lemma 6. For m as in Lemma 3 we have the equality m = dim F2 Span F2 1; 1=2 0 ; : : : ; 1; 1=2 n 1 :

(1)

The eld K is the exact constant eld of F (i.e. K is algebraically closed in F) and F is the compositum of the rst m elds F i over K(z), i.e. F = F 0 F m 1 .

The Galois group of F=K(z) is isomorphic to (Z=2Z) m . The action of 2

Gal(F=K(z)) is given by ( s i ) = s i or ( s i ) = s i + 1, where s i is a root of the left hand side of the i-th equation of F in F, for 0 i n 1. Proof. Consider the operator }(x) = x 2 + x and the additive group (or F 2 -module) 0 = Span F2 z 1 + 0 + 1=2 0 z; : : : ; z 1 + n 1 + 1=2 n 1 z : We further de ne = 0 + } K(z) . With this we have F

= K(z) } 1 ( ) = K(z) } 1 ( 0 ) and m = dim F2 =} K(z) = dim F2 0 = 0 \ } K(z) ;
where the rst equality holds according to Theorem 4 and the second equality holds according to the rst isomorphism theorem for groups.

We have 0 \} K(z) = 0 \}(K) because applying } to non-constant functions in K(z) would necessarily involve quadratic terms in z which are not to be found in 0 . Let us abbreviate U = Span F2 1; 1=2 0 ; : : : ; 1; 1=2 n 1 . Expanding the elements in 0 into vectors in K 2 by taking the coe cients of z 1 and z gives a surjective linear map 0 ! U. Its kernel is 0 \ K. But every element of the kernel must be a sum of an even number of the j because otherwise the z 1 would not cancel. From Lemma 5 we conclude that 0 \ K = 0 \ }(K), and using 0 \ }(K) = 0 \ } K(z) , we obtain 0 = 0 \ } K(z) = U. The formula for m is thereby veri ed.

In order to prove that K is the exact constant eld of F we have to show that \ K }(K) (remember F = K(z) } 1 ( ) ). But again every u 2 \ K is congruent to a sum of an even number of the j modulo }(K). Lemma 5 gives u 2 }(K) and K is hence algebraically closed in F.

The statement about the compositum is seen as follows: The rst m terms in the de nition of 0 constitute a basis of the F 2 -vector space 0 . This is due to the property that, if the i-th term is dependend of the previous j-th terms for 0 j i 1, then the i + 1; i + 2; : : : terms would be as well because they arise by applying to the i-th term. Hence F is obtained by adjoining roots of the rst m left hand sides of F to K(z) from which the statement follows.

From Theorem 4 and F : K(z)] = 2 m we obtain Gal(F=K(z)) = (Z=2Z) m .

The action of 2 Gal(F=K(z)) is as stated because xes all z 1 + i + 1=2 i z by de nition and hence has to map roots of s 2 i +s i +z 1 + i + 1=2 i z to themselves.

3.3. Hyperellipticity and genus. Adding the 0-th equation to the i-th equation of F for i = 1; : : : ; m 1 and substituting t i for s 0 + s i , i for 0 + i and i for 1=2 0 + 1=2 i we obtain t 2 i + t i + i z + i = 0; i = 1; : : : ; m 1:

(2)

These equations de ne extensions L i of K(z) such that F = F 0 L with L = L 1 L m 1 the compositum of the L i over K(z). The eld L is crucial to establishing the hyperellipticity, since it de nes a rational sub eld of index two, as we shall now show.

Lemma 7. The eld L is an extension eld of degree 2 m 1 of K(z). It is a rational function eld L = K(c) having a generator c such that z = 1 + P m 1 i=0 i c 2 i with i 2 K and 0 ; m 1 6 = 0.

Proof. The extension eld statement follows from 2 L : K

(z)] = F : L] L : K(z)] = F : K(z)] = 2 m .
We now apply inductively some further transformations to (2). We wish to determine a change of variables so that we obtain equations of the form t 2 i + t i + i t i 1 + i = 0; i = 1; : : : ; m 1;

(3) where t 0 = z.

We take the rst equation of (2) (i = 1) to be the rst equation of (3). Now suppose after already having performed some transformations (with t i , i and i substituted properly), for some j 2 2; : : : ; m 1], we are given equations t 2 i + t i + i t i 1 + i = 0; i = 1; : : : ; j 1; t 2 i + t i + i z + i = 0; i = j; : : : ; m 1 de ning the extension L=K(z) as well. All left hand sides of these equations must be irreducible due to the choice of m and hence we must have i 6 = 0 since K is algebraically closed in F, by Lemma 6. Because of this, being true also for the next intermediate i , we can carry out the following transformations: By substituting t j + ( j = 1 ) 1=2 t 1 for t j and using the above equation with i = 1 we obtain t 2 j + t j + j 1 1=2 + j 1 ! t 1 + j 1 1 + j = 0; wherein we write j for the coe cient of t 1 and j for the constant term. Next, we use the equation for i = 2 to eliminate t 1 in the same way as was done with z = t 0 , and we repeat this for t 2 ; t 3 ; :::; t j 2 ; we eventually arrive at t 2 j + t j + j t j 1 + j = 0; as desired. By induction we go on until j = m.

Next, by expressing z = (t 2 1 + t 1 + 1 )= 1 , t 1 = (t 2 2 + t 2 + 2 )= 2 , and so on, we obtain z = 1 + P m 1 i=0 i c 2 i with c = t m 1 and suitable i 2 K. Since L=K(z) is separable and L : K(z)] = 2 m 1 , we nally see that 0 ; m 1 6 = 0.

To estimate the genus of our function eld we shall use the following theorem, which is a special case of 18, Proposition III.7.8, pp. 115]: Theorem 8. Let L=K denote a rational algebraic function eld of characteristic two. Suppose that u 2 L is an element which satis es the following condition: u 6 = w 2 + w for all w 2 L:

Let F = L(y) with y 2 + y = u. For a place P of L we de ne the integer m P by

m P = 8 > > < > > :
m if there is an element z 2 L such that v P (u + (z 2 + z)) = m < 0 and m 6 0 (mod p)

1 if v P (u + (z 2 + z)) 0 for some z 2 L:

If at least one place Q of L satis es m Q > 0 then K is algebraically closed in F, and g = 1 2 2 + X P (m P + 1) deg P ! ;

where g is the genus of F.

Lemma 9. F=K is a hyperelliptic function eld of genus 2 m 1 or genus 2 m 1 1 over the exact constant eld K.

Proof. The constant eld statement is proved in Lemma 6. Recall, we have F = F 0 L and F : L] = 2. Hence, the hyperellipticity is clear, since L is rational by Lemma 7.

Next we prove the genus statement. In order to obtain F from L we need to adjoin to L a root of the left hand side of the 0-th equation de ning F. We take a closer look at the constant term (in s 0 ) of this equation u = 1=z + 0 + 1=2 0 z 2 L, where we think of z as a polynomial in c of degree 2 m 1 as in Lemma 7.

Since this polynomial is separable, it factors in K c] into irreducible polynomials with all multiplicities equal to one. The valuations v P (u) of u at the places P above z = 0 of the rational function eld L (i.e. those places satisfying v P (z) > 0) are thus all 1 and we obtain m P = 1. We additionally know P vP (z)=0 deg P = 2 m 1 , this is easily seen as we are working in a rational function eld.

We now consider the degree valuation 1 of L = K(c). Since z = 1 + P m 1 i=0 i c 2 i there are ũ; v 2 K c] such that 1=2 0 z = ũ+v 2 +v and deg(ũ) 1. The polynomial v can be obtained e. g. by successively eliminating leading terms using elements of the form ( c) 2 i + ( c) 2 i 1 . Thus v 1 (u + v 2 + v) 1 and m 1 = 1 or m 1 = 1.

The remaining places P of L have v P (u) = 0 hence m P = 1. Summing up, using Theorem 8, we nally obtain g = 2 m 1 or g = 2 m 1 1.

3.4. Restriction to smaller constant eld. Up to now we have used the Artin-Schreier nature of the equations de ning D (resp. F) in an essential way, in order to obtain the statements on the hyperellipticity and the genus. Next, we need to restrict to a smaller constant eld, and here we will use the existence of a Frobenius automorphism on F which is due to the very construction of D.

Lemma 10. The Frobenius automorphism of K over k extends (non uniquely) to a k-automorphism on F of order n or 2n, again denoted by .

We have roots s i = i ( s 0 ) of the left hand sides of F and accordingly roots w i = i ( w 0 ) of the left hand sides of D with w i = x s i + 1=2 i for all 0 i n 1. Proof. The Frobenius automorphism extends to a k-automorphism of K(x) = K(z) by leaving x, resp. z, xed.

The eld F is obtained from K(z) by successively adjoining roots s i for 0 i m 1 of the left hand sides of F to K(z). Once these m roots s i are adjoined roots s i of the other equations for m i n 1 are readily to be found in F and will be de ned on them. For m = 1 we can simply de ne ( s 0 ) = s 0 . Assume we have m > 1 and : K(z)( s 0 ; : : : ; s i 1 ) ! F for an i with 0 i < m 1. We can extend to K(z)( s 0 ; : : : ; s i ) ! F by choosing ( s i ) = s i+1 because the left hand side of the i-th equation of F is irreducible over K(z)( s 0 ; : : : ; s i 1 ) and applying to z 1 + i + i z gives z 1 + i+1 + i+1 z. Hence we can extend to the whole of F by de ning on s i for 0 i m 1.

The order of any such on F must be a multiple of n since K F and has order n on K. Furthermore, n ( s 0 ) = s 0 or n ( s 0 ) = s 0 + 1 because n ( s 0 ) must be a root of the left hand side of the rst equation of F. We conclude that the order of on F will be n or 2n accordingly.

The statement on the roots is clear and serves primarily as a de nition for later use.

It is at this point that condition (y) becomes important.

Lemma 11. If condition (y) is satis ed then the extension in Lemma 10 of the Frobenius to F can be chosen with order exactly n on F.

Proof. We now need to derive a precise condition for the order of such extensions . It will turn out that we have to carefully choose a particular extension if we want to obtain order n. The precise condition will be obtained from the precise value of n ( s 0 ), and is then compared to condition (y).

To begin with we start with any extension of the Frobenius to F which will be changed later as required. It is convenient to employ the following technique: For f(t ) = P i d i t i 2 F 2 t ] we de ne f(t )s = P i d i i (s) where s 2 F arbitrarily, thereby turning F + into an F 2 t ]-module. As a subgroup K + inherits this F 2 t ]module structure which is compatible with the F 2 t]-module structure of K + used in the proof of Lemma 5 under the relation t = t r for r = log 2 (q). We let f 0 (t ) be the polynomial of smallest degree such that f 0 (t ) 0 = 0 and set f(t ) = f 0 (t ) for deg f 0 (t ) even;

(t + 1)f 0 (t ) otherwise.

The same polynomials f 0 and f are obtained upon replacing 0 with 1=2 0 . From Lemma 6 and its proof it is easily seen that deg f(t ) = m.

Since (t n + 1) 0 = 0 there is an h(t ) 2 F 2 t ] such that h(t )f(t ) = t n + 1.

We have f(t ) s 0 2 + f(t ) s 0 = f(t ) s 2 0 + s 0 = f(t ) z 1 + 0 + 1=2 0 z = f(t ) 0 : Now, as f(1) = 0, we can apply Lemma 5 to the last right hand side above and nd a v 2 K with v 2 +v = f(t ) 0 . Here we actually have a choice between v and v +1 which will be important later. Adding v 2 + v to the rst left hand side above we obtain f(t ) s 0 + v 2 f0; 1g. It is now that we have to choose the correct extension of , depending on the choice of v: If we have f(t ) s 0 + v = 1 we replace by a 0 which satis es 0 ( s i ) = ( s i ) for 0 i < m 1 and 0 ( s m 1 ) = ( s m 1 ) + 1, which we can do according to the extension process at the beginning of the proof.

Since the leading term of f(t ) is t m and s m 1 = m 1 ( s 0 ) we can hence assume f(t ) s 0 + v = 0:

(4)

Multiplying this with h(t ) yields (t n + 1) s 0 + h(t )v = 0 from which we draw the conclusion: has order n on F if and only if h(t )v = 0. The rest of the proof deals with the relation of this condition and (y), and the suitable choice of v.

Using the proof of Lemma 5 and the above compatibility remark we see that we can choose between v = f(t r )=(t+1) 0 and v = f(t r )=(t+1) 0 +1. Multiplying the rst v with h(t r ) we obtain h(t r )f(t r )=(t+1) 0 = (t rn +1)=(t+1) 0 = Tr K=F2 ( 0 ). Thus, depending on the choice of v,

h(t )v = Tr K=F2 ( 0 )
or Tr K=F2 ( 0 ) + h(1):

(5) Our k-automorphism on F, depending on v, has order n if and only if we obtain zero for at least for one of the cases in the right hand side of [START_REF] Cantor | Computing in the Jacobian of a hyperelliptic curve[END_REF]. But this is implied by (y): The case Tr K=F2 ( 0 ) = 0 is clear. For n odd we obtain h(1) = 1 because t + 1 divides t n + 1 only once. For n = m we obtain h(t ) = 1 hence h(1) = 1 too.

We remark that the conditions (y) are su cient but not necessary for the existence of an extension of the Frobenius automorphism of K=k to F of order n. Precise conditions can be derived from [START_REF] Cantor | Computing in the Jacobian of a hyperelliptic curve[END_REF] and may be summarized as follows: \ The extension exists either for all 2 K or only for those 2 K with Tr K=F2 ( ) = 0, given any xed 2 K ". Theorem 12. Let be an extension of the Frobenius automorphism of K=k to F, having order n, and let F 0 be the eld of elements of F xed by . The eld F 0 is a hyperelliptic function eld of genus 2 m 1 or 2 m 1 1 over the exact constant eld k. The curve C has an irreducible reduced component having F 0 as its function eld.

Such a k-automorphism exists if the condition (y) is satis ed.

Proof. We let L 0 = F 0 \ L. The relations between the elds F; F 0 ; L and L 0 are described by Figure 1.

The xed eld F 0 of has index n in F because is of order n on F and it is clear that F 0 \ K = k holds because is of order n on K as well.

k n 1 @ @ @ @ @ K k(x)

2 m 1 1 n @ @ @ @ K(x) K(E) @ @ @ @ 2 L 2 m 1 L 0 @ @ @ @ @ 2 n F 2 F 0 @ @ @ @ n Figure 1. Lattice Diagram of Fields
The automorphism restricts to a k-automorphism of L of order n because it is the unique sub eld of F of index 2 and K L. Thus, L : L 0 ] = n, since L 0 is the xed eld of restricted to L and we obtain F 0 : L 0 ] = 2, as desired. Clearly F = F 0 K (and also L = L 0 K) which gives the genus statement.

From the w i we obtain n, not necessarily distinct, elements y i via the linear transformation of Lemma 2. The automorphism operates cyclically on the w i so that we have ( y i ) = y i , as was proved generically in Lemma 2. The y i are thus in F 0 and together with x they generate F 0 over k (because the w i can be obtained from the y i over K). Due to Lemma 2 the y i satisfy the equations of C, from which we nally see that C has an irreducible reduced component with function eld F 0 (we can for example again use the kernel technique from the proof of Lemma 3).

The existence of under condition (y) was proved in Lemma 11.

Note, that if condition (y) is not satis ed and has order 2n, then we could have F 0 = L 0 in the arguments of the proof of Theorem 12, and hence we could not guarantee nding a curve de ned over k which is hyperelliptic and has genus 2 m 1 or 2 m 1 1.

If the value of m is too small then none of the irreducible components of C will have a Jacobian which contains a subvariety isogenous to the subvariety B of A. For example, let E(F q n ) denote a Koblitz curve, i.e. one de ned over the eld F 2 .

We will then obtain irreducible components of C of genus one, by the de nition of m. In this case, the Weil restriction A factors as the product A = E(F q ) B where B is an n 1-dimensional abelian variety de ned over F q . The curve in the Weil restriction we have constructed has irreducible components whose Jacobians are isogenous to E(F q ) and so we obtain no information about the subvariety B from our curves. This does not mean that one cannot nd useful curves in A, whose Jacobian contains a subvariety isogenous to B. It just means that the curves we have constructed are not useful in this context. This is why we have assumed throughout that E is not de ned over a proper sub eld of K.

In view of Theorem 12 and Lemma 11 we assume for the rest of Section 3 that we are given an extension of the Frobenius automorphismus of K=k on F of order n and that operates cyclically on the s i and w i while leaving x and z xed. This can be reached when the condition (y) is ful lled.

3.5. Determination of an explicit model for F and F 0 . We describe how to obtain Artin-Schreier equations de ning F over L and F 0 over L 0 . The corresponding hyperelliptic equations are easily obtained by similar (reversed) transformations as done in the beginning of 3.2.

To compute an Artin-Schreier equation in s 0 and c for F over L for the generators s 0 2 K(E) F and c 2 L, we only need to substitute 1 + P m 1 i=0 i c 2 i 1 for z in the rst equation s 2 0 + s 0 + z 1 + 0 + 1=2 0 z = 0 of F, due to Lemma 7. In order to determine the action of on F we need to compute i (c) and i ( s 0 ) for 0 i n 1 as expressions in c and s 0 . This can be done using the operation of as given in (4) and by tracing back the transformations of Lemma 7. Note that c is a K-linear combination of z and the i ( s 0 ) for 0 i m 1 and that each of these can in return be expressed in c (z = f(c) resp. i ( s 0 ) = f i (c) + s 0 for suitable f; f i 2 K c]). Given c and s 0 and the action of on c and s 0 we can explicitly construct F 0 and L 0 as follows: Lemma 13. Choose 2 K such that Tr K=k ( ) = 1 and set c = Tr L=L 0( 0 c), s = Tr F=F 0 ( s 0 ). We then have L 0 = k(c) and F 0 = k(s; c). An Artin-Schreier equation de ning the eld F 0 over L 0 is given by s2 + s + 1=z + Tr K=k ( 2 ) + Tr K=k ( 2 1=2 ) z

+ Tr F=F 0( 2 s 0 ) + Tr F=F 0( s 0 ) = 0;

where the absolute coe cient in s of the left hand side of this equation, the element z and hence the last line Tr F=F 0( 2 s 0 ) + Tr F=F 0( s 0 ) are in L 0 .

Proof. From the extension structure L=K(z), because z = 1 + P m 1 i=0 i c 2 i and (z) = z, it is clear that maps poles of c to poles of c. Since L is rational we see that there are ; 0 2 K such that (c) = c + 0 . Then

(z) = 1 + m 1 X i=0 i c 2 i ! = ( 1 ) + m 1 X i=0 ( i ) 02 i + 2 i c 2 i :
On equating coe cients in (z) = z, we obtain for i 0 ( i ) 2 i = i :

For i = 0 we thus obtain ( 0 c) = ( 0 )( c + 0 ) = 0 c + ( 0 ) 0 :

Now from this c = Tr L=L 0( 0 c) = 0 c + 00 for some 00 2 K and thus L 0 = k(c).

Consider the Galois group of F=K(z). According to Lemma 6 it is an elementary abelian 2-group whose elements send each i ( s 0 ) to i ( s 0 ) or i ( s 0 ) + 1. Now let be the hyperelliptic involution on F=L, being an element of this Galois group. Since xes L and any of the i ( s 0 ) generates F over L we must have ( i ( s 0 )) = i ( s 0 ) + 1 = i ( ( s 0 )) for all i. We thus see that and commute in their action on F and that hence operates by restriction on F 0 =L 0 . We again consider the equations de ning F. Using Tr K=k ( ) = 1 we obtain (s) = s + 1 and Tr F 0 =L 0(s) = s + (s) = 1: Using s2 = Tr F=F 0( 2 s 2 0 ) = Tr F=F 0( 2 ( s 0 + 1=z + + 1=2 z))

we obtain for the norm N F 0 =L 0 (s) = s(s + 1) = 1=z + Tr K=k ( 2 ) + Tr K=k ( 2 1=2 ) z + Tr F=F 0 ( 2 s 0 ) + Tr F=F 0( s 0 ) :

Putting together we thus arrive at equation ( 6). This equation is separable in s, and by construction it has coe cients in L 0 . Looking at the equations de ning F gives that the valuation of s i at the zeros of z is only half the valuation of 1=z. The term in the second line of ( 6) is a K-linear combination of the s i and, as element of L 0 , has therefore no poles except at c = 1. It is hence a polynomial in c and we can conclude that the left hand side of ( 6) is indeed irreducible.

The elements s and c can be computed in F using . The absolute coe cient in equation ( 6) is rst computed in K(c) and lies in k(c) after substituting c = (c + 00 )= 0 .

We let y = x s 0 + 1=2 and ỹ = Tr F=F 0 ( y) so that ỹ = xs + Tr K=k ( 1=2 ). In the case of odd n we can choose = 1 and obtain the equation ỹ2 + xỹ + x 3 + Tr K=k ( )x 2 + Tr K=k ( ) = 0; for x the inverse of the separable polynomial 1 + P m 1 i=0 i ((c + 00 )= 0 ) 2 i 2 k c].

We remark that in this case the genus of F 0 =k is 2 m 1 1 if Tr K=k ( ) = 0. 3.6. Mapping the discrete logarithm problem. We next address the question of mapping the discrete logarithm problem from E to F 0 , where we again use the function eld setting. We let Cl 0 (K(E)) denote the group of divisor classes of degree zero of the function eld K(E) of E, and similarly for Cl 0 (F ). The divisor class of the divisor D is written D].

The conorm Con F=K (E) and norm N F=F 0 maps we de ne as in 5, pp. 65] (cf. 18, pp. 63 and 239]), on recalling that F is a function eld extension of both K(E) and F 0 . Both conorm and norm are homomorphisms of divisor groups, are well de ned on divisor classes and map divisor classes of degree zero to divisor classes of degree zero.

The point group E(K) of the elliptic curve E is isomorphic to the group of divisor classes of degree zero of K(E) 16, p. 66, Prop. 3.4]. The mapping of the discrete logarithm problem in the point group E(K) of E is then achieved as follows: First we translate the problem into Cl 0 (K(E)). From there we use the conorm Con F=K (E) in order to map it to Cl 0 (F ), and from there, using the norm N F=F 0, to Cl 0 (F 0 ). On composition we thus obtain a group homomorphism : E(K) ! Cl 0 (F 0 ):

The important question now is whether the large cyclic factor of E(K) of order p is preserved by this homomorphism. Lemma 14. The kernel of Con F=K(E) : Cl 0 (K(E)) ! Cl 0 (F ) can only consist of 2-power torsion elements of Cl 0 (K(E)). Proof. Let D be a degree zero divisor of K (E). We have according to 5, pp. 66, line 21] that N F=K(E) (Con F=K(E) (D)) = F : K(E)]D: Thus, if Con F=K(E) (D) is principal, then F : K(E)]D is also principal. But F : K(E)] = 2 m 1 which means that D] has 2-power order.

According to the lemma the large cyclic factor can only be mapped to zero under by the norm N F=F 0 .

For very small values of m, such as those obtained for Koblitz curves, the kernel of will necessarily be divisible by the large prime p. But if m is larger than log 2 (n), then the large prime factor of the order of E(K) will be preserved in many instances. Hence, to solve our discrete logarithm problem P 2 = l]P 1 on E(K) we map degree zero divisor classes representing P 2 and P 1 over to Cl 0 (F 0 ) using the map . Set D 1 = (P 1 ) and D 2 = (P 2 ). If we do not obtain D 1 = D 2 = 0, which in practice is unlikely unless the elliptic curve is actually de ned over a sub eld of K, we can attempt to solve the discrete logarithm problem D 2 = l]D 1 in Cl 0 (F 0 ).

The computation of images under is in principle feasible by general methods, such as those used for computations with algebraic number elds and their extensions. Nevertheless, we want to give some rough indications on a method for our case. We assume that we can compute su ciently well with nite elds and that we can de ne the function eld of an irreducible a ne plane curve, that we can compute the decomposition into places of the principal divisor of an element and of e ective divisors and that we can evaluate elements at places. Let P 1 be a place of K(E) of degree one where x; y 2 K(E) take the values x(P 1 ); y(P 1 ) 2 K respectively (we assume for simplicity that x(P 1 ) 6 = 0; 1). The place P 1 is clearly the unique common zero of x + x(P 1 ) 2 K(E) and y + y(P 1 ) 2 K(E). Then Con F=K(E) (P 1 ) can be computed as the greatest common divisor of the numerators of the principal divisors x + x(P 1 ) and y + y(P 1 ) taken in F.

It is a divisor of degree 2 m 1 according to 5, pp. 65, Lemma 1].

Let P be a place of F dividing Con F=K(E) (P 1 ) for some place P 1 of K(E) of degree one (we decompose Con F=K(E) (P 1 ) to compute P). The place L \ P can be described as the numerator of f(c) , where f is the minimal polynomial of c(P ) over K and the principal divisor is taken in L. This is possible as c has no pole at P because x(P) = x(P 1 ) 6 = 0, which we have assumed above (c and ỹ are de ned after Lemma 13 and given as elements of F and generators of F 0 ). The place P can similarly be given as follows: Let h be a bivariate polynomial over K such that h( ; c(P )) is the minimal polynomial of ỹ(P ) over K(c(P)). ỹ is de ned at P because all of the i ( y) are as x(P) 6 = 1. We may represent P as the the greatest common divisor of the numerators of f(c) and h(ỹ; c) , where the principal divisors are taken in F. This divisor consists of only P without multiplicities because as x(P 1 ) 6 = 0 we have that L \ P is unrami ed in F, hence there are at most two places in the numerator of f(c) and each of them occurs with multiplicity one. Furthermore, if the other place Q 6 = P above L \ P exists then h( ; c) has degree one as the residue class degree of P over L \ P is one. We also obtain ỹ(Q) = ỹ(P ) + x(P) 6 = ỹ(P ) and h(ỹ(Q); c(Q)) 6 = 0, hence Q does not occur in the numerator of h(ỹ; c) (cf. 18, p. 76, Thm. III.3.7.] and its proof, h is one of the ' i and ' is the minimal polynomial of ỹ over K(c)). We are actually interested in determining the underlying place P 0 = F 0 \ P of F 0 , so we need to express the situation with coe cients in k rather than K.

For this we simply compute minimal polynomials f; h as above, but over k instead, and compute P 0 as the greatest common divisor of the numerators of f(c) and h(ỹ; c) , where the principal divisors are now taken in F 0 . This divisor consists of only P 0 without multiplicities because of the same reasons as above.

Finally, N F=F 0 (P ) = f(P; P 0 )P 0 where f(P; P 0 ) = n deg(P )= deg(P 0 ) is the residue class degree of P over P 0 . We will have that N F=F 0 (Con F=K(E) (P 1 )) is e ective and that its degree equals n2 m 1 , for the later taking 5, pp. 66, Lemma 2] and its proof into account.

A program for computing F 0 and given E has been written in KASH and is planned to be written for inclusion in the Magma computer algebra system.

Constructing Hyperelliptic Cryptosystems

Our method for constructing hyperelliptic cryptosystems is now immediate.

1. Fix a eld k = F q and an integer n such that K = F q n . 2. Choose an E over K of order 2 l p where p is a prime and l is a small integer. This can be achieved by generating curves at random and computing their group orders using the algorithm of Schoof 15]. 3. Construct the Weil restriction and the curve C as we did in Section 3.

4. Find a model H of an irreducible component of C in hyperelliptic form. 5. Check that the divisor class group of H over k has a subgroup of order p. The nal condition is necessary since we only know that a subvariety of A is isogenous to a subvariety of the Jacobian of H. Clearly in step 2 we should only choose curves for which condition (y) will automatically hold, i.e. n odd or Tr K=F2 ( ) = 0.

If in the above algorithm we choose n = 4, b 3 = b 0 + b 1 + b 2 , with the special examples of Section 2, we will expect to obtain a hyperelliptic curve of genus 3 or 4, de ned over k, whose Jacobian will, in general, have order 2 l p. If l is chosen small then we do not expect to obtain genus 3. If we choose n = 2, and a very small value for l, then we expect to obtain a hyperelliptic curve of genus 2, de ned over k, whose Jacobian has order divisible by p.

4.1. Genus Four Example. We consider an example where p 2 80 . Clearly this is not large enough for cryptographic use, but we use it for illustrative purposes, both here and later. Curves with p > 2 160 are just as easy to produce, they just require more paper to write down.

Consider the eld k = F 2 21 generated over F 2 by a root of the polynomial: w 21 + w 2 + 1: Let K = F 2 84 be generated over k by a root of the polynomial 4 + 3 + 2 + + 1: We construct the elliptic curve

E : Y 2 + XY = X 3 + b 0 + b 1 2 + b 2 4 + b 3 8
where b 0 = 0; b 1 = w 1127280 ; b 2 = w 171398 ; b 3 = w 1370436 : Notice that b 3 = b 0 + b 1 + b 2 , and so we expect to obtain a hyperelliptic curve of genus four. The order of E(K) is computed using the algorithm of Schoof 15] and it is equal to 2 4 p, where p = 1208925819614311295169073:

Our algorithm for producing a curve of genus four in the Weil restriction produces the curve C 4a , of Section 2. This curve has Jacobian also of order 2 4 p. But the curve C 4a is birationally equivalent to the following hyperelliptic curve, which we calculated using the method in Section 3,

H : Y 2 + G(X)Y + F(X) = 0 (7)
where G(x) is given by X 4 + w 624429 X 3 + w 1248858 X 2 + w 1442662 X + w 386860 and F(X) is given by X 9 + w 1859582 X 6 + w 293124 X 4 + w 1783647 X 3 + w 1541982 X 2 + w 1370912 X + w 1888298 : 4.2. Genus Two Example. We construct an elliptic curve over the eld K = F 2 162 with group order equal to 5846006549323611672814739995379292203636332479268 which is four times a prime, p. We do not give the details of this elliptic curve here for reasons of space. The Weil restriction, and our construction of the associated hyperelliptic curves, produces the following example of a genus two hyperelliptic curve de ned over k = F 2 81 . De ne k by k = F 2 w]=(1 + w 4 + w 81 ). The Jacobian of the hyperelliptic curve of genus two given by H : Y 2 + (X 2 + w 2012013793551629036365609 X)Y = X 5 + X 4 + w 1586464037343056940725724 X 2 +w 43334222987849600951547 X + w 774788345987798314632240 has order divisible by p. Its group structure is given by C 2 C 2p and it is not subject to the Tate-pairing attack 8] since p does not divide q k 1 for small values of k.

Notice, that if the original elliptic curve E(F q n ) resists the Tate pairing attack, i.e. there does not exist a small value of k for which q nk 1 1 (mod p), then the analogous test for the Jacobian is obviously satis ed for small values of k.

Attacking Elliptic Curve Cryptosystems

The question remains as to whether the above construction provides either a mechanism to attack elliptic curve cryptosystems or whether the hyperelliptic cryptosystems proposed above are strong. In this section we discuss the di culty of solving the discrete logarithm problem in the Picard group of the hyperelliptic curves we have constructed. We shall assume a xed, small, value of n and we look at the situation as q tends to in nity.

For any group, the rho method (with Pohlig-Hellman) provides an algorithm for computing the discrete logarithm in time O( p p) where p is the largest prime factor of the order of the group. For general elliptic curves, this is the best known algorithm. For the curves de ned over F q n considered in this paper we obtain a complexity of O(q n=2 ) in general.

For hyperelliptic curves, we can obtain a better complexity by using an indexcalculus method. If the curve is de ned over F q and the genus is not too high (say at most 8), we can proceed as follows. We consider a factor base containing all the prime divisors of the Jacobian of degree one. We can then proceed in two phases. In the rst phase, relations are found between the elements of the factor base, whilst in the second phase we perform sparse linear algebra to solve the original discrete logarithm problem. The details of this algorithm are in 10], but we give some details in an example below.

Theorem 15 (Gaudry 10]

). There is an index calculus style algorithm to solve the hyperelliptic discrete logarithm problem in a hyperelliptic curve of genus g over the eld F q which requires a factor base of size O(q) and which runs in time O g 3 g!q log q + O g 3 q 2 log q for some xed integer .

Hence, for xed values of g the complexity of this algorithm is O(q 2+ ), which is better than the rho method for a (almost) cyclic Jacobian of genus at least 5. However, it is unclear where the exact crossover point between the method of 10] and the rho method lies.

The theoretical complexity can be improved by reducing the size of the factor base. The smoothness bound is already minimal, but we can decide that some of the prime divisors of degree one are `good' (we keep them in the factor base), whereas others are rejected. If we set the proportion of `good' divisors to 1=l, then the time for nding a relation will be increased by a factor l g . However, we will need l times less such relations, and the cost of the linear algebra will be reduced by a factor 1=l 2 . If we try to optimize the choice of l, we obtain l = ((q=g!) 1=(g+1) ) and the complexity becomes O(q 2g g+1 + ), as q ! 1.

In the following table we give the complexities of the discrete logarithm problem on the elliptic curves studied in the previous sections and on the corresponding Jacobians. We only look at the genera which are likely to occur in practice for the example curves in Section 2 and we ignore the q term in the complexity estimate.

Notice that for the `interesting' subvariety of Jac(C) in our Weil-descent examples the complexity of the rho method on Jac(C) is equal to the complexity of the rho method on E(F q n ). For a general Jacobian of genus g the rho method has complexity O(q g=2 ).

Example Curve C 2 C 3 C 3 C 4 C 4 C 4a n, g 2,2 3,3 3,4 4,8 4,7 4,4

rho on E(F q n ) q q 3=2 q 3=2 q 2 q 2 q 2 Index on Jac(C) q 4=3 q 3=2 q 8=5 q 16=9 q 7=4 q 8=5

We stress that these complexities hold as q tends to in nity and with n and g xed. Hence, for g 4 we obtain a complexity which is better than that of Pollard rho.

In a context where we would like to build a hyperelliptic cryptosystem by a Weil descent, the Jacobians have to be almost cyclic, which occurs for the cases C 2 , C 3 and C 4a . For the rst two, this seems to be a good way to build a cryptosystem in genus two or three; however, for the last one the index-calculus provides an attack with a better theoretical complexity than the rho method, and the security is asymptotically lower than with an elliptic curve cryptosystem with the same key size.

On the other hand, if we want to attack an elliptic curve cryptosystem, we see that for C 4 and C 4a the complexity of index-calculus is better than for the rho method. Thus, asymptotically, it is a good way to attack such elliptic curve cryptosystems by transferring the problem to a hyperelliptic curve.

However, experiments have to be done for each xed value of n and g to see where is the crossover between the two attacks, since the group operations in E(F q n ) and in Jac(C) will have di erent complexities. Such an experiment is carried out in the next section.

Solving a Hyperelliptic DLOG Problem

It is important to decide, not only for the Weil descent attack but also for our construction of hyperelliptic cryptosystems in genus four, whether the method of 10] is practical in genus four. In this section we consider the example given by the curve in equation (7). The elds size is q = 2 21 and the curve has genus 4, so the Jacobian has size approximately 2 84 . We will solve a discrete logarithm problem in this group using the method of 10] and then compare the running time to known e cient implementations of the rho method in an elliptic curve group of the same size. Since the rho method applied to a hyperelliptic curve will run slower than on an equivalently sized elliptic curve, if the method of 10] runs faster on the hyperelliptic curve compared to rho on an elliptic curve we will know that Genus four systems are less secure than the equivalent elliptic curve system, for eld sizes greater than 2 21 . We would then conclude that genus four hyperelliptic systems should not be deployed in real life.

Elliptic curves de ned over F q n , with m = 3 and q = 2 t , are weaker than those de ned over F 2 p with p prime and of the order of nt.

We attempted to solve the discrete logarithm problem given by D 2 = l]D 1 where D 1 = (X 4 + w 1277131 X 3 + w 1087066 X 2 + w 1391819 X + w 1964994 ; w 1784094 X 3 + w 131164 X 2 + w 1975559 X + w 2073352 ); D 2 = (X 4 + w 895988 X 3 + w 1765969 X 2 + w 1667155 X + w 1531893 ; w 110642 X 3 + w 2014036 X 2 + w 927941 X + w 1063447 );

where the divisors are given in the reduced representation as in the paper by Cantor 4]. In this notation, the point at in nity is implicitly subtracted with the correct multiplicity in order to obtain a divisor of degree zero. The above divisor D 1 is a generator of the subgroup of prime order p 2 80 .

The factor base consists of all prime divisors of the form p = (X + ; ) where ; 2 k = F q , and 2 + G( ) + F( ) = 0:

To each there are two corresponding values of , but we only choose one of these to be in our factor base, since the two prime divisors are related by the equation:

(X + ; ) + (X + ; G( ) + ) 0;
in the divisor class group.

To reduce the factor base even further we only use divisors in the factor base such that the binary representation of has a bit representation with its three most signi cant bits set of zero. Where the bit representation is in the polynomial basis with respect to w. Such prime divisors will be called `good'. In our example the number of such good divisors which make up our factor base F is 131294.

Consider the following general reduced divisor D = (a(X); b(X)) with deg b < deg a g. A necessary condition for this divisor to factor over our factor base of `good' divisors will be for the binary representation of a deg a 1 , the (deg a 1)th coe cient of a(X), to have its three most signi cant bits set to zero. This gives us a simple test to eliminate lots of divisors which are not smooth over our set of good divisors.

The algorithm proceeds as follows. We compute a set of `random' multipliers M i = r i ]D 1 + s i ]D 2 ; for 1 i 20; for some random integers r i and s i . Then setting R 1 = M 1 , say, we compute the following random walk

R i+1 = R i + M h(Ri)
where h : Jac(H) ! 1; : : : ; 20] is some hash function. Notice that every value R i can be written as

R i = a i ]D 1 + b i ]D 2 :
We then try to `factor' R i over our factor base to obtain a relation of the form R i = X p2F t p ]p:

Due to our choice of factor base this factorization can be achieved using root extraction techniques over nite elds rather than general polynomial factoring techniques. We eliminate many divisors, before we apply root extraction, by our test for smoothness over the good divisors which we described above. The resulting t p lie in g; : : : ; g], where for our example g = 4. We store the t p in a matrix as a column, which will have at most g non-zero entries in each column. Almost all relations we obtain will have t p 2 f 1; 0; 1g and will have exactly g non-zero values of t p in each column.

After collecting more relations than elements in our factor base we can apply sparse matrix techniques modulo p, such as the Lanczos method, to nd a nontrivial element in the kernel of the matrix. Using the element in the kernel we can then nd the solution to the original discrete logarithm problem, with overwhelming probability, in the standard manner. We ran the above algorithm on the above example. The relation collection phase took about two weeks of calendar time, using the idle time of a disparate set of machines. If we had ran this task on a single Pentium II 450 MHz, the timing would have been about 31 weeks. The linear algebra step took 64:4 hours using the same machine. After which we determined the solution to D 2 = l]D 1 was given by l = 12345678:

An equivalent calculation on an 84 bit elliptic curve, using Pollard's rho method, would have taken 44 weeks on the same machine, with a program with a similar level of optimizations applied. Since the crossover point is for a value of q less than what would be used in practice, we can conclude that genus four hyperelliptic systems are weaker than an elliptic curve system with the same size group order.

Other Types of Finite Fields

7.1. Non-composite Fields Of Even Characteristic. In Section 5 we looked at what happens when n is xed and we let q tend to in nity. In practice the elliptic curves over even characteristic elds which are used are ones de ned over F 2 p , with p a prime. Hence, we need to look at the situation where q is xed and n tends to in nity. Let E denote an elliptic curve, de ned over F 2 p where p is prime. We expect that the methods of this paper would produce a hyperelliptic curve of genus 2 p 1 over the eld F 2 . It seems unlikely that one would, in general, be able to nd a curve of signi cantly smaller genus in the Weil restriction of E(F 2 p ) over F 2 .

However, using equation (1) one may be able to nd, in very special circumstances, certain elliptic curves which have values of m slightly larger than log 2 p, for which there exist curves in the Weil restriction of genus slightly larger than p, as the following example shows:

Consider K = F 2 w]=(1 + w + w 127 ) and the elliptic curve de ned by (a; ) = (0; w), i.e. E : Y 2 + XY = X 3 + w: The number points on E(K) is computed to be #E(F 2 127 ) = 2 20 3 2 45615671 395232781659164075412101:

Along the arguments of Section 3 we computed its Weil restriction for n = 127 down to F 2 , obtaining the hyperelliptic curve H : y 2 + (x 128 + x 64 + x)y + x 128 + x 64 + x = 0:

The curve H has genus 127 and its Jacobian contains an element of order #E(F 2 127 )=2:

We constructed this example by trying to make m as small as possible. It appears that one can obtain very small values of m for a zero of a polynomial with only 2-power coe cients, in the above case 128 + 2 + = 0. Another similar value for may be obtained by a zero of the irreducible factor of degree 127 of x 2 10 + x 2 + x over F 2 .

In general, for random , a small value of m is very unlikely as we shall now show. Lemma 16. We expect at least fty percent of all the elliptic curves over K = F 2 p , for p prime to produce a value of m equal to p.

Proof. By a change of variables we can put our curve in the form Y 2 + XY = X 3 + X 2 + where = 0 or 1 and 2 K. Now by the de nition of m in (1), if f ; 2 ; : : : ; 2 p 1 g is a normal basis of K over F 2 then m = p. But around fty percent of all elements of K generate a normal basis, as we shall now show. By Lemma 3.69 and Theorem 3.73 of 12] the number of elements, 2 K, which generate a normal basis over F 2 is equal to

2 p t Y i=1 (1 2 ni )
where n i denotes the degrees of the distinct monic irreducible factors of the polynomial X p 1 over F 2 . But by Theorem 2.47 of the same book we see that this is equal to 2 (p 1)=d 1 d = O(2 p 1 ); where d is the number of distinct factors of the polynomial X p 1 + X p 2 + + X + 1 over F 2 . Hence, around fty percent of all elements in K generate a normal basis.

For general curves, where m = p and g = 2 p 1 , one needs to bear in mind that although there is a sub-exponential algorithm for the discrete logarithm problem on hyperelliptic curves of large genus, it is sub-exponential in the size of the Jacobian which will be of the order of 2 g = 2 2 p 1 : But we are really aiming for a sub-exponential algorithm in the size of the original elliptic curve, which is 2 p . On the other hand, for the very special elliptic curve in the above example, we indeed obtain a possible subexponential attack. Note that the method of 10] should not be used in this case since it is only e cient for `small' genera.

To obtain a sub-exponential algorithm for very large genera the methods from 1, 9, 11, 13] should be combined after suitable modi cation for our hyperelliptic even characteristic case.

Hence, for curves de ned over non-composite elds of characteristic two, we do not expect the techniques in this paper to contribute a signi cant threat to elliptic curve cryptosystems. This last statement holds assuming curves are either chosen with values of m of the order of p, or are chosen to be curves which are de ned over F 2 , i.e. a Koblitz curve. 7.2. Odd Characteristic Fields. The question arises as to whether the process of Weil descent can be applied to elds of the form F p n where p is an odd prime. Clearly we must have n 2 and by similar arguments to those above n should not be too large.

The proofs in Section 3 relied heavily on the Artin-Schreier nature of the extensions. It appears hard to see how they can be modi ed to apply in the odd characteristic case. Indeed in the few examples we have calculated we see that the resulting curves neither have such nice genera nor are they hyperelliptic in nature. Hence, using odd characteristic elds does not seem helpful in constructing higher genus hyperelliptic cryptosystems.

Let us turn to attacking elliptic curve systems based on elds of the form F p n . This is an open problem which we now outline with an example: Consider the eld F p 3 = F p t]=(t 3 + 3491750t 2 + 217412320t + 795426309) where p = 1073741839 = 2 30 + 15. An elliptic curve de ned over F p 3 is given by Y 2 = X 3 + AX + B where A = 787621733t 2 + 572191144t + 6271705; B = 167167209t 2 + 739374709t + 362095083:

For this curve it is easily veri ed that the group order is #E(F p 3 ) = 2 4 59 2261143 579962087855207501: Setting X = x 0 + x 1 t + x 2 t 2 and Y = y 0 + y 1 t + y 2 t 2 one can construct the Weil restriction.

Suppose the method of Gaudry could be extended to arbitrary Jacobians and not just hyperelliptic Jacobians with almost prime group orders. This at rst sight does not seem too implausible but is the subject of ongoing research 6]. One would expect the resulting algorithm to have complexity at best O(p 2g g+1 ). Hence, to beat the asymptotic complexity of Pollard's rho method on E(F p 3 ) we would require a curve of genus at most 3.

Naively mimicking our method of Weil descent in characteristic two one forms the curve C de ned by the hyperplanes x 1 = x 2 = 0, i.e. specializing to those x-coordinates which are xed under the Frobenius automorphism. The resulting curve has genus 13 and is not hyperelliptic. Trying di erent types of bases for F p 3 over F p and di erent hyperplanes does not appear to result in anything better. This is an avenue for further work and the construction of a suitably well behaved curve in the Weil restriction cannot be ruled out at present.

Conclusion

Let E(F q n ) denote an elliptic curve over a eld of even characteristic, which is not de ned over a sub eld of F q n and which satis es condition (y). Then we have shown how the Weil restriction produces a hyperelliptic Jacobian of genus at most 2 n 1 which, for examples of cryptographic interest, contains a subgroup isomorphic to a subgroup of E(F q n ).

Using this observation we can construct hyperelliptic cryptosystems by rst constructing elliptic curves using the Schoof algorithm and then determining the associated hyperelliptic curve. This appears to be a way to produce secure hyperelliptic cryptosystems in genus two and three. We recommend against using this method in genus four and above because of our experiment in solving discrete logarithm problems in genus four, where we showed that the discrete logarithm problem in the Jacobian of a curve of genus four was easier than on an elliptic curve of the same group order, with a security level of at least 80 bits.

However, for xed values of n 4, this provides evidence for the weakness of the original elliptic curve discrete logarithm problem. We have shown that for n = 4 and around 1=q of all such curves the crossover point, between our method and Pollard rho, is at a value of q less than 2 21 . However, for larger xed values of n, say n = 11 or 13, the crossover between our method and Pollard rho will be much higher. Hence, further experiments are needed in determining the exact crossover point between the two methods for various values of n.

We have no evidence to suggest that the discrete logarithm problem on general elliptic curves, de ned over elds of the form F 2 p where p is prime, has complexity smaller than O(2 p=2 ). Since these are the elds of characteristic two which are recommended in the elliptic curve standards, Weil descent does not appear to be a threat to standards compliant elliptic curve systems in the real world. However, we do recommend that elliptic curves de ned over F 2 p , for p prime, should be checked to be sure that they produce a value for m in equation (1) which is of order around p or equal to one, as in the case of curves de ned over F 2 . Only curves with these values for m should be deployed in real world cryptosystems. In practice most elliptic curves over F 2 p will satisfy such a requirement, but it is worth adding this check to curve generation programs and to standards documents.


J Provost
email: provost@lurpa.ens-cachan.fr

J.-M Roussel
email: roussel@lurpa.ens-cachan.fr

J.-M Faure
email: faure@lurpa.ens-cachan.fr

SIC-testability of sequential logic controllers

Keywords: Conformance test, Model-based test, Test sequence generation, Logic systems, Testability criterion

SIC (Single Input Change) test sequences must be privileged for conformance test of logic controllers, to prevent from erroneous test results when the test-bench and the implementation under test are not synchronized. This paper proposes first a definition of the SIC-testable part of a sequential specification model, i.e. the part of the model that can be tested by using a sequence starting from the initial state and for which only one input can change at one at the same time. Then, an algorithm to determine the SIC-testable part is given; if this part is the whole specification, the specification model is declared totally SIC-testable. Once the SICtestable part obtained, a SIC sequence for conformance test of an implementation of this part can be generated. These contributions are exemplified on an example.

INTRODUCTION

Logic controllers are increasingly used in critical systems, like power production and distribution systems or transport systems, even for safety-related functions. To ensure dependability of these systems, it really matters to check, before operation, whether each controller behaves correctly with respect to its specification. This is the aim of conformance test, a black-box test technique that is experimentally performed (Figure 1) by sending to the controller an input sequence and comparing the observed output sequence, controller's response to the input sequence, to the expected output sequence so as to build the test verdict: the implemented controller is conform or not. The set of the input sequence and expected output sequence is termed test sequence.

Fig. 1. Conformance test execution

In industrial practice, test sequences are often built manually on the basis of the designer's experience and skill; this is a very tedious, time-consuming and error-prone task.

To solve this issue, it is possible to take benefit from the numerous theoretical results that have been published in the domain of conformance test, assuming that the specification is formally described, for instance in the form of a finite state machine [START_REF] Lee | Principles and methods of testing finite state machines -a survey[END_REF], da Silva Simão et al. ( 2009)), a transition system [START_REF] Tretmans | Model based testing with labelled transition systems[END_REF]) or a particular class of Petri net [START_REF] Von Bochmann | Testing k-safe Petri nets[END_REF]). [START_REF] Provost | Test sequence construction from SFC specification[END_REF]), for instance, presents a method to translate a specification described in an industrial standardized language into a finite state machine to take benefit from the results on conformance test of these models. Generally speaking, these works provide a way to build automatically a welldefined test sequence from the specification model and to deliver a verdict from the observed output sequence. The test sequence is constructed so as to meet a test objective that is formally defined: exhaustiveness (all transitions are visited at least once) and minimum-length, non-occurrence of unexpected sequence of events, reachability of states, . . . The SIC (Single Input Change) or MIC (Multiple Input Change) feature of the input sequence is never considered, though. In a SIC input sequence, named SIC sequence in the remainder of this paper for simplicity reasons, (Figure 2), the value of only one input can change at one and the same time; synchronous values changes are not allowed. This is not the case in a MIC input sequence. These concepts are used for electronics circuits testing where SIC sequences are privileged to limit power consumption [START_REF] Yi | An implementation of random single input change technique for low-power test[END_REF]) or to increase the efficiency of delay fault testing [START_REF] Virazel | Delay fault testing: Choosing between random sic and random mic test sequences[END_REF]). Power consumption limitation is not a significant concern during the test of a logic controller and only non-timed systems are addressed in this work. SIC sequence generation is to be investigated however because such a sequence prevents from erroneous test results (biased results if a conform implementation is declared non-conform or non-valid results if implementation errors are not detected) when the test-bench and the logic controller are not synchronized. In this case indeed, when a MIC input sequence is generated by the test-bench, synchronous inputs changes may be seen asynchronous by the controller under test. For technological reasons, all inputs are not read simultaneously by the controller and, in case of two synchronous changes, it may get the value of one input just before its change and the value of another input just after its change. In figure 2 b), the simultaneous changes of a and b at date t 1 that are issued from the testbench may be interpreted by the controller in one of the following fashions:

t 0 t 1 t 2 t 3 t 4 t 5 a) SIC sequence
• Simultaneous changes of a and b;

• Change of a just followed by change of b;

• Change of b just followed by change of a.

It could be argued that a simple solution is to synchronize the bench and the controller; this is not technically so simple and often impossible if non-invasive test is compulsory. This explains why generation of SIC sequences deserves to be investigated.

It is always possible and easy to build a SIC sequence for a combinatorial logic system by arranging the inputs values according to the Gray code. This is no more the case when sequential systems are focused on; in this case indeed, the aim of the test sequence is to explore a part or the totality of the evolutions and some evolutions may require simultaneous inputs changes. Then, the aim of this work is to propose a method to determine the SIC-testable part of the specification model, i.e. the part that can be explored by using a SIC sequence which starts from the initial state. If this part corresponds to the whole specification, the specification is declared totally SIC-testable. Once the SIC-testable part defined, a SIC sequence for conformance test of an implementation of this part can be built.

Analysis of the SIC-testability requires a formal definition of a test sequence that relies on inputs-outputs values. This implies to model the behavior of the logic controller on the same bases. This behavioral model is proposed in section 2, while the model and properties of the test sequence are given in section 3. Section 4 shows how the SIC-testable part can be obtained by a fixed-point calculation and section 5 deals with SIC sequence construction. Some prospects for further research are sketched in section 6.

MODELING THE BEHAVIOR OF SEQUENTIAL LOGIC CONTROLLERS

Several event-based formalisms have been proposed to model sequential systems; they have permitted to obtain worthwhile theoretical results in the domains of synthesis and analysis of DES. However, when design, implementation and test of sequential logic controllers are considered, it is more convenient to select a modeling formalism whose inputs and outputs are logic variables, and not events, and that allows a behavior be represented by a state machine whose transition conditions depend on combinations of inputs values. This section aims to define this formal model.

Definitions

Formally, a Sequential Logic Controller (SLC) is defined by a 3-tuple (I, O, B) where:

• I is a non-empty set of logic inputs.

• O is a non-empty set of logic outputs.

• B is the behavior of the controller.

As inputs are logic variables and not events, they can be combined together to give inputs valuations. If the cardinality of I is |I|, there exist 2 |I| distinct inputs valuations v I . Let us note V I the set of the inputs valuations and V O the set of the outputs valuations. As an inputs valuation of a given set I of logic inputs is a Boolean combination, it can be represented by a minterm1 .

A sequence of inputs valuations is an ordered list of inputs valuations and will be noted as follows:

v 0 I , v 1 I , • • • , v n I ∈ V * I (1)
The behavior B of a SLC is defined by a 4-tuple (S, s Init , δ, λ), where:

• S is a non-empty set of states.

• s Init is the initial state, s Init ∈ S.

• δ is the transition function, defined as follows:

δ : S × V I → S (s, v I ) → s = δ(s, v I ) (2)
• λ is the output function, defined as follows:

λ : S → V O s → v o = λ(s) (3)

Properties of a SLC

By definition, the behavior B of a SLC is deterministic: there is only one initial state and δ and λ are two functions. Moreover, to avoid misinterpretation errors during the test, the behavior B must be:

• completely defined: δ and λ are total functions2 (equation 4); • reduced to its only reachable part (equation 5); • without transient evolution (equation 6), i.e. no inputs change introduces successive changes of states.

∀(s, v I ) ∈ S × V I , ∃!δ(s, v I ) ∈ S ∃!λ(s) ∈ V O (4) ∀s ∈ S, ∃[v 0 I , • • • , v n I ] ∈ V * I |    s 1 = δ(s Init , v 0 I ) ∀k > 1, s k = δ(s k-1 , v k-1 I ) s = s n (5) ∀(s, v I ) ∈ S × V I , δ(s, v I ) = δ(δ(s, v I ), v I ) (6)

Illustration on an example

The above definitions and properties will be illustrated Each cell of the table contains the value of δ(s, v ). A circled state name means that the same state is both source and target of the transition (self-loop structure). The output function is merely defined by:

λ(s 1 ) = CG • OG ; λ(s 2 ) = CG • OG ; λ(s 3 ) = CG • OG ;
The behavior given table 1 is deterministic and completely defined since every cell contains one and only one state name. This behavior does not contain any transient evolution since the value of each cell is either a circled value or leads to a cell with a circled value. For example, when the active state is s 1 , for the inputs valuations c

• o • r • v, the system evolves towards state s 3 . Since δ(s 3 , c • o • r • v) = s 3 , no other evolution is possible without a new change of inputs valuation.
This tabular description cannot be used obviously for non-trivial examples. Hopefully, it can be replaced by an equivalent graphical description (Figure 4) in which a Boolean expression E ij is associated to each transition from state s i to state s j . This expression represents the set of inputs valuations that cause this transition. For the example, E 12 for instance is True only for the two inputs valuations c•o•r•v and c•o•r•v, then E 12 represents the set of these two inputs valuations. This behavior can be obtained automatically from standardized language [START_REF] Provost | Test sequence construction from SFC specification[END_REF].

The determinism and completeness conditions can then be respectively reformulated as follows:

∀(s i , s j , s k ) ∈ S 3 , s j = s k ⇒ E ij • E ik = Exp AlwaysF alse (7) ∀s i ∈ S, sj ∈S E ij = Exp AlwaysT rue (8)
where Exp AlwaysF alse and Exp AlwaysT rue correspond to the Boolean expressions "always False" and "always True".

The condition on absence of transient evolution becomes:

∀(s i , s j ) ∈ S 2 , E ij • E jj = Exp AlwaysF alse (9) s 1 s 2 s 3 start E 12 E 23 E 31 E 13 E 32 E 21 E 11 E 22 E 33 λ(s 1 ) = ∅ λ(s 2 ) = {CG} λ(s 3 ) =
E 11 = o • (c + r + v) + c • r E 22 = c • r • v E 33 = o E 12 = c • r • v E 13 = o • (r + c • v) E 21 = o • (c + r + v) + c • r E 23 = o • r + c • o • v E 31 = o • (c + r + v) E 32 = c • o • r • v

Formal definition of test sequences

During test execution, a test sequence is seen as an ordered list of couples (inputs valuation,expected outputs valuation) which represents its external view:

(v 0 I , v 0 O ), (v 1 I , v 1 O ), ..., (v n I , v n O ) ∈ (V I × V O ) * (10)
Conformance test implies that the expected outputs valuation is obtained from the behavior model. More precisely, this valuation is associated to the target state of the evolution that is provoked by the inputs valuation, when the model is in a given source state. To obtain this expected valuation, the source state (s s ) and target state (s t ) must compulsorily be known. Hence, an elementary conformance test step et is defined by the following 4-tuple:

et = (s s , v I , s t , v O ) ∈ S × V I × S × V O where s t = δ(s s , v I ) v O = λ(s t ) = λ(δ(s s , v I )) (11)
Thus, a test sequence is an ordered list of elementary test steps and a consistent test sequence T S is a test sequence such as the source state of the k th elementary test step is equal to the target state of the (k -1) th step.

T S = [(s 0 , v 0 I , δ(s 0 , v 0 I ), λ(δ(s 0 , v 0 I ))), • • • , (s n , v n I , δ(s n , v n I ), λ(δ(s n , v n I )))] | ∀k > 1, s k = δ(s k-1 , v k-1 I ) (

Properties of test sequences

A test sequence T S may be:

• initializable, i.e. the source state of the first test step is the initial state:

s 0 = s Init (13)
• exhaustive, i.e. there is at least one test step for each element of the transition function:

∀(s, v I ) ∈ (S × I), (s, v I , δ(s, v I ), λ(δ(s, v I ))) ∈ T S (14)
• based on a SIC inputs sequence.

To express formally this latter property, the SIC relation between two inputs valuations must be first defined In the remainder of this paper, this symmetrical relation is noted: v I R Gray v I . It can be noted that n SIC relations can be stated for each inputs valuation v I of a SLC with n logic inputs.

Hence, a test sequence T S is based on a SIC inputs sequence and termed SIC test sequence if and only if:

∀k > 1, v k I R Gray v k-1 I (16)

Illustration on the example

In table 1, each cell may be associated to a test step whose source state, inputs valuation and target state are respectively given by the corresponding line, column and content of the cell. An initializable and exhaustive test sequence must start from a cell of the first line (initial state: s 1 ) and cover all cells of the table. A consistent test 3 dim(A) is the dimension of set A. v I \v I is the subset of I composed with elements of v I which are not in v I .

sequence corresponds to only horizontal and vertical cells changes according to the following rules:

• From the cells that contain a circled state name (the source and target states of the associated test step are identical), only horizontal changes are possible. The inputs valuations of two successive test steps can be different, but the source state of the second step must be identical to the target state of the first one. • From the cells that contain a non-circled state name (the source and target states of the associated test step are different), only one vertical change is possible. This change leads to the cell that belongs to the line of the target state of the first test step.

It is easy to see that only the first case must be considered to determine whether the test sequence is a SIC test sequence, i.e. the inputs valuations v I and v I of all couples of successive test steps satisfy v I R Gray v I . However, it is not always possible to build an exhaustive SIC test sequence from a behavioral model. For the example, the cell (s

2 , c•o•r •v) cannot be reached from cells (s 2 , c•o•r •v) or (s 2 , c • o • r • v)
with only a SIC inputs sequence.

Then, SIC-testability of the behavioral model, ability of this model to be used to construct a SIC, initializable and exhaustive test sequence, must be checked before test sequence construction. This is the objective of the next section.

CHECKING SIC-TESTABILITY OF A SLC

This section aims to show that the SIC-testability of a SLC can be checked by a fixed-point calculation on elementary test steps. Before presenting this contribution, some details on conformance test execution must be reminded. An elementary test step is executed as follows:

• First, the test-bench sends to the controller under test the inputs valuation. • Then, the test-bench waits that the controller computes its outputs; this waiting time is function of the technological features of the controller (filtering time, scanning cycle duration, . . . ) and will not be more discussed in this paper.

v I : Inputs valuations c • o • r • v c • o • r • v c • o • r • v c • o • r • v c • o • r • v c • o • r • v c • o • r • v c • o • r • v c • o • r • v c • o • r • v c • o • r • v c • o • r • v c • o • r • v c • o • r • v c • o • r • v c • o • r • v (s 1 , CG • OG) 1 s 2 1 s 3 1 s 3 1

Principle

The proposed method is based on the following two observations:

•

(n + 1) = R SIC (n) ∪ (s k , v k+1 I , δ(s k , v k+1 I ), λ(δ(s k , v k+1 I ))) ∪ (δ(s k , v k+1 I ), v k+1 I , δ(s k , v k+1 I ), λ(δ(s k , v k+1 I )) | ∃(s k , v k I ) ∈ R SIC (n) | δ(s k , v k I ) = s k v k+1 I R Gray v k I (17)
At the end of this iterative calculation, the controller is SIC-testable if the final set contains all test steps that can be defined from its behavior description. Otherwise, this final set defines the SIC-testable part.

As a real logic controller can always be put in its initial state before being tested, it was chosen to start the fixedpoint calculation with the following set:

R SIC (0) = (s Init , v 0 I , s Init , λ(s Init )) | v 0 I ∈ V I , δ(s Init , v 0 I ) = s Init (18)

Illustration on the example

Table 2 presents the results of this calculation for the example. The number k of the iteration during which the test step was found SIC-testable is at the top-left corner of each cell. For example, the step associated to the cell (s 1 , c • o • r • v) is obtained at iteration 0 (initialization), because this step corresponds to a self-loop on s 1 . The step associated to the cell (s Hence, the behavior of this controller is NOT SIC-testable; its SIC-testable part is given by the cells which are not colored.

1 , c • o • r • v) is obtained in step 1, as c • o • r • v R Gray c • o • r • v,

Implementation for graphical descriptions of behavior

As already mentioned, the tabular representation is not suitable to specify non-trivial controllers. Hence, the fixedpoint calculation has been transformed to deal with graphical descriptions of the behavior. The core idea of this transformation is to manipulate the inputs valuations through Boolean expressions and not explicitly. Algorithm 1 has been then developed to automate SICtestability analysis.

This algorithm relies mainly on an operation noted Expansion Gray that is based on symbolic calculus and permits to expand a given set V A I of inputs valuations v I with the inputs valuations v I which satisfy v I R Gray v I . The expanded set is noted V B I :

V B I = V A I ∪ {v I | ∃v I ∈ V A I : v I R Gray v I }, (19)
Let us consider Exp A the Boolean expression which represents the set V A I . The set V B I is described by the following Boolean expression:

Exp B = Expansion Gray (Exp A ) = i∈I Exp A |i←F alse + Exp A |i←T rue (20)
The example below illustrates this operation.

V A I = {c • o • r • v , c • o • r • v , c • o • r • v} Exp A = c • o • r + c • o • v Exp B = (o • r + o • v) + (c • r + c • v) + (c • o) + (c • o) = c • o + c • r + c • v + o • r + o • v V B I = {c • o • r • v , c • o • r • v , c • o • r • v , c • o • r • v , c • o • r • v , c • o • r • v , c • o • r • v , c • o • r • v , c • o • r • v , c • o • r • v} (21)

bFig. 2 .

 2 Fig. 2. Example of SIC and MIC test sequences

  Fig. 3. Inputs/Outputs of the example

Fig. 4 .

 4 Fig. 4. Graphical representation of the behavior 3. SIC TEST SEQUENCE DEFINITION

  . The definition below is based on the representation of an inputs valuation by the subset of I that contains the only variables which are True for this valuation. Thus, two inputs valuations v I and v I satisfy a SIC relation if and only if 3 : dim((v I \v I ) ∪ (v I \v I )) = 1 (15) For example, the inputs valuations which are represented by the minterms c•o•r •v and c•o•r •v satisfy a SIC relation since dim(({r, v}\{c, r, v}) ∪ ({c, r, v}\{r, v})) = dim(∅ ∪ {c}) = 1

  on the example of figure 3. This controller owns 4 inputs (c, o, r and v), and 2 outputs (CG and OG); then, 16 inputs valuations (v I ) and 4 outputs valuations (v O ) can be defined. If the state space comprises 3 states (s 1 : initial state, s 2 and s 3 ), the transition function is defined on 48 couples (s, v

I ); an enumerated description of this function is given in table 1, in which each line corresponds to a state s and each column to an inputs valuation v I . Column 2, for instance, represents the inputs valuation such that c, o and r are False and v is True; this valuation can be represented either by the minterm c•o•r•v or by the subset of I that contains the only variables which are True for this valuation {v}.

  {OG}

	Notation: • means AND,
	+ means OR, and
	¯means NOT

Table 1 .

 1 Example of behavior given in an extensional form

	12)

•

  Once the controller's outputs computed and stable, the test-bench compares the real outputs valuation to the expected one. The next step can then start.

	P P (s, v O ): P P (States,Outputs valuations) P P P P P P P	P P	P	P P P

Table 2 .

 2 Illustration of the steps of the fixed point calculation of the SIC region It matters to underline that, during the waiting time of the elementary test step (s s , v I , s t , v O ), the test step (s t , v I , s t , v O ), which specifies that v I does not modify the active state when this state is s t , is also automatically executed.

  An elementary test step (s s , v I , s t , v O ) for a behavior B is SIC-testable if it can be included into an initializable SIC test sequence for this behavior. Owing to the test execution features, the elementary test step (s t , v I , s t , v O ) is also SIC-testable. • If the elementary step (s t , v I , s t , v O ) is SIC-testable, it is always possible to add to the test sequence an elementary step (s t , v I , δ(s t , v I ), λ(s t , v I )) where v I satisfies: v I R Gray v I .

	On these bases, the set of elementary test steps which are
	SIC-testable can be obtain by the following fixed point
	calculation:
	R SIC

  and so on. Calculation stops at the third iteration, excluding the initialization. The final set contains only 40 test steps; the steps that do not belong to this set are represented by colored cells.

A minterm is the product of all the n Boolean input variables in the positive or complemented form.

∃!: There exists exactly one.

This work is funded by the French National Research Agency (TESTEC project,

T estableP art := T SIC (s i ) print "SIC-Testable part of ",s i ,": ",T estableP art end for

CONSTRUCTION OF THE SIC TEST SEQUENCE

This construction is based on a graph whose nodes represent all couples (s, v I ) that can be defined on the SICtestable part. The arcs (directed edges) between the nodes are defined as follows:

• only one arc starts from a node that corresponds to a couple (s, v I ) such as δ(s, v I ) = s; the target node of this arc is the node that corresponds to (δ(s, v I ), v I ); ss: s 1 s 1 s 2 s 3 s 3 s 2 s 2 s 3 s 1 s 1 s 3 s 1 s 1 s 3 s 3 s 1 s 1 c:

1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 o: 0 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 0 r: 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 v: 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 st: s 1 s 2 s 3 s 3 s 2 s 2 s 3 s 1 s 1 s 3 s 1 s 1 s 3 s 3 s 1 s 1 s 3 s 3 s 1 s 3 s 3 s 1 s 3 s 3 s 1 s 2 s 1 s 2 s 1 s 3 s 1 s 2 s 1 s 2 s 2 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0