On the use of expansion series for stream ciphers

Claus Diem

April 5, 2012

Abstract

From power series expansions of functions on curves over finite fields, one can obtain sequences with perfect or almost perfect linear complexity profile. It has been suggested by various authors to use such sequences as key streams for stream ciphers. In this work, we show how long parts of such sequences can be computed efficiently from short ones. Such sequences should therefore considered to be cryptographically weak. Our attack leads in a natural way to a new measure of the complexity of sequences which we call expansion complexity.

1 Introduction

It is well known that linearly recurrent sequences, that is, sequences generated from linear feedback shift registers (LFSR), are cryptographically weak. This observation leads to the following well-established definitions; cf. [18],

[16] and other works on linearly recurrent sequences.

We set ℕ := {1, 2, …}. Let q be a prime power. By a sequence over 𝔽_{q} we mean a map from a subset of the form {1, …, m} or from ℕ to 𝔽_{q}. For a finite sequence a = (a_{1}, a_{2}, …, a_{n}) over 𝔽_{q} one defines the linear complexity, L_{a}, as the least ℓ such that a is generated by a linear recurrence relation of order ℓ. Now, for a finite or infinite sequence a = (a_{1}, a_{2}, …) of length m over 𝔽_{q} and for n ≤ m, one defines L_{a}(n) as the linear complexity of the finite subsequence consisting of the first n terms of a, and one defines the linear complexity profile as (L_{a}(n))_{n=1}^{m}.

An infinite sequence a = (a_{i})_{i∈ℕ} over a finite field 𝔽_{q} is said to have perfect linear complexity profile if |2L_{a}(n) − n| ≤ 1 for all n and d-almost perfect linear complexity profile if |2L_{a}(n) − n| ≤ d for all n.

In [20] a general construction of sequences with almost perfect complexity profile was given. The construction is based on function expansion into expansion series and will be recalled below. The motivation stated in [20] to consider this construction is the generation of key streams for stream ciphers. Also in [16] the consideration of the construction is motivated by applications to stream ciphers.

In this work, we show that the coefficients of the sequences constructed via the method in [20] can be efficiently computed from relatively short subsequences. Therefore, the sequences should be considered as cryptographically weak.

The proposed attack leads to a new notion of complexity which we call expansion complexity. The expansion complexity of a sequence is always at most the linear complexity and captures the immunity against our attack.

Additionally, we show how one can apply well known results on continued fraction expansion in order to obtain further inside into the series suggested in [20]. In particular, we refute the conjecture in [20] that all sequences with almost perfect linear complexity profile can be obtained with the construction in [20].

This work is organized as follows: In the next section, we briefly recall how one is naturally lead from linearly recurrent sequences to expansion sequences. The third section is devoted to an analysis via continued fraction expansion. In the forth section, we give the theoretical background of our attack, and in the fifth section, we discuss computational aspects. The final section contains a discussion and some research proposals based on our attack.

Some definitions Let k be a finite field. By a function field over k we mean a finitely generated extension of k of transcendence degree 1. Let F/k be a function field with exact constant field k (which means that k is algebraically closed in F), and let f ∈ F be non-constant (that is, f ∉ k). Then we define the degree of f as deg(f) := [F : k(f)]. Thus the degree of f is the degree of f as a function on the corresponding complete non-singular curve over k. In particular, the degree of a non-constant rational function r = \frac{a}{b} ∈ k(t) with coprime polynomials a, b ∈ k[t] is max\{deg(a), deg(b)\}. Additionally, we define the valuation degree of r as valdeg(r) := deg(a) − deg(b). We therefore have v_{∞}(r) = − valdeg(r). We caution the reader to not confuse the degree of a rational function with the valuation degree. The latter will only be used in Section 3 on continued fractions.

Acknowledgments I thank Andrei Shelest and Natalia Vasilevskaya for introducing me to the idea to generate random sequences by power series expansions and for discussions. I thank Enric Nart for a discussion on Hensel’s Lemma.

2 From linearly recurrent sequences to power series expansions

Let us first recall some facts about linear complexity. These facts lead naturally to the consideration of continued fraction expansions and to the construction in [20].

Let still q be a prime power, and let a = (a_{1}, a_{2}, …) be an infinite sequence over 𝔽_{q}. Then we have the associated generating series

s := ∑_{i∈ℕ} a_{i}t^{i} ∈ 𝔽_{q}[[t]] .

With x := t^{−1} ∈ 𝔽_{q}(t) we obtain that

s = ∑_{i∈ℕ} a_{i}x^{−i} ∈ 𝔽_{q}[[x^{−1}]] .

Both these descriptions of the series s are of importance in the following.

The sequence a is generated by a linear feedback shift register with generating polynomial g(x) if and only if s · g is a polynomial in x, which is then automatically of degree < deg(g). Therefore, a is linearly recurrent with recursion order d if and only if s is a rational function in x of degree d. Moreover, we have L_{n}(a) ≤ ℓ if and only if there exists a rational function f ∈ 𝔽_{q}(x) of degree at most ℓ with s = f +O(x^{−(n+1)}), where the O-notation is used as in infinitesimal calculus.

It is now natural to consider the continued fraction expansion of s to study the linear complexity profile of a. This is done in [14] and in [16]. In the next section we recall some results obtained in this way and make some more observations. Here, we mention just one basic result which can be obtained in this way (see Proposition 2 in the next section):

As above, let a be an arbitrary infinite sequence over 𝔽_{q} and let d ∈ ℕ. Then a has d-almost perfect linear complexity profile if and only if L_{n}(a) ≥ \frac{1}{2}(n + 1 − d) for all n ∈ ℕ.

Whereas the first description of the sequence s is important for the analysis via continued fraction expansion, it is the second description which leads naturally to the construction via function expansion into power series as described in [20] and also in [16]. We observe that s is a rational function of degree d in x if and only if it is a rational function of degree d in t. Therefore, s is linearly recurrent with recurrence order d if and only if s is a rational function of degree d in t.

Let now F/𝔽_{q} be a function field with exact constant field 𝔽_{q}, and 𝔓 be a place of degree 1 of F and t a uniformizing element at 𝔓. Then we have an associated homomorphism of function fields F ↪ 𝔽_{q}((t)). The image of some f ∈ F is called the expansion of f with respect to t. Now for any f with v_{P} (f) ≥ 1, we obtain a power series ∑_{i∈ℕ} a_{i}t^{i}, and we can consider the series (a_{i})_{i∈ℕ} defined by the coefficients.

For example, if F = 𝔽_{q}(t), that is, if t has degree 1, then we obtain a linearly recurrent sequence with recurrence order deg(f). By the above considerations, it is particularly natural here to consider expansions of functions f ∈ 𝔽_{q}(x) with respect to the “place at infinity” (with respect to x), 𝔭_{∞}, and the local uniformizer t := x^{−1}.

It is proven in [20] that if t has degree 2 and f is in F − 𝔽_{q}(t) and has degree d then the sequence (a_{i})_{i∈ℕ} has d-almost perfect linear complexity profile. More generally, for arbitrary non-constant t we have

L_{a}(n) ≥ \frac{n + 1 − deg(f)}{deg(t)}

for all n ∈ ℕ.

Let us recall the easy proof: Let ℓ := L_{a}(n). Then we have polynomials r, u ∈ 𝔽_{q}[t] with deg(r) ≤ ℓ, deg(u) ≤ ℓ, u(0) = 0 and

s · r ≡ u mod t^{n+1} .

This is equivalent to

f · r ≡ u mod 𝔓^{n+1} ,

i.e.

v_{𝔓}(f · r − u) ≥ n + 1 .

This implies that deg(f ·r −u) = deg(f ·r −u)_{0} ≥ n+1. On the other hand, f ·r−u ∈ L((f)_{∞} +ℓ·(t)_{∞})−{0} and thus deg(f ·r−u) ≤ deg(f)+ℓ·deg(t). We conclude that n + 1 ≤ deg(f) + ℓ · deg(t).

Definition We call a power series in 𝔽_{q}((t)) obtained by expansion of any function as just described an expansion series (over 𝔽_{q}). Furthermore, if a is a series which is the sequence of coefficients of an expansion series (which then lies in t · 𝔽_{q}[[t]]), then we call the sequence a an expansion sequence (over 𝔽_{q}).

3 Analysis with continued fraction expansion

Again let q be a prime power. We consider continued fraction expansions of elements of 𝔽_{q}((x^{−1})). We expend the valuation degree function from 𝔽_{q}(x) to 𝔽_{q}((x^{−1})) by valdeg(∑_{i≥n} a_{i}x^{−i}) := −n if a_{n} ≠ 0, and we set v_{∞}(f) := − valdeg(f) and |f| := q^{−v_{∞}(f)} = q^{valdeg(f)}. Clearly, | · | is a nonarchimedean absolute value, and 𝔽_{q}((x^{−1})) is the completion of 𝔽_{q}(x) with respect to this absolute value.

Let now a be an infinite sequence over 𝔽_{q}. We consider the continued fraction expansion of s = ∑_{i∈ℕ} a_{i}x^{−i}. Let us first fix some standard definitions and recall some basic results. We mainly follow [16] here.

Let

s = [0; A_{1}, A_{2}, A_{3}, …]

be the continued fraction expansion of s. Here by definition, the A_{i} are polynomials in 𝔽_{q}[x]; they are called the partial quotients of s.

As usual, we define

p_{−1} := 1 , p_{0} := 0 , p_{i} := A_{i}p_{i−1} + p_{i−2} for i ∈ ℕ

and

q_{−1} := 0 , q_{0} := 1 , q_{i} := A_{i}q_{i−1} + q_{i−2} for i ∈ ℕ .

Then for each i, the polynomials p_{i} and q_{i} are coprime, and we have

\frac{p_{i}}{q_{i}} = [0; A_{1}, …, A_{i}]

and

deg(q_{i}) = ∑_{j≤i} deg(A_{i}) .

We set w_{i} := deg(q_{i}).

In [14] the following proposition is proven (see also [16]).

Proposition 1 Let n ∈ ℕ. Let now j be defined by the following inequalities

w_{j−1} + w_{j} ≤ n < w_{j} + w_{j+1} .  (1)

Then L_{n}(a) = w_{j}.

A consequence of this proposition is:

Proposition 2 Let d ∈ ℕ. Then the following conditions are equivalent:

a) The sequence a has d-almost regular complexity profile.

b) L_{n}(a) ≤ \frac{n+d}{2} for all n ∈ ℕ.

c) L_{n}(a) ≥ \frac{n+1−d}{2} for all n ∈ ℕ.

d) deg(A_{i}) ≤ d for all i.

Later we will consider a variant of this proposition. For this reason, we now recall the proof given in [16].

Clearly, a) implies b) and c). We show that b) implies d) and that c) implies d).

Let i ∈ ℕ with w_{i} ≥ 1 and let n := w_{i−1} + w_{i}. Then L_{n}(a) = w_{i} and n = 2w_{i} − deg(A_{i}) = 2L_{n}(a) − deg(A_{i}). Therefore deg(A_{i}) = 2L_{n}(a) − n. If now b) is satisfied then deg(A_{i}) ≤ d.

Let now i ∈ ℕ with deg(A_{i}) ≥ 2 and let n := w_{i−1} + w_{i} − 1. Then L_{n}(a) = w_{i−1} and n = 2w_{i−1}+deg(A_{j})−1 = 2L_{n}(a)+deg(A_{j})−1. Therefore deg(A_{i}) = n + 1 − 2L_{n}(a). If now c) is satisfied then again deg(A_{i}) ≤ d.

We now show that d) implies b) and c) and therefore also a).

Let n ∈ ℕ. Then inequalities (1) are equivalent to

2w_{j} − deg(A_{j}) ≤ n < 2w_{j} + deg(A_{j}) ,

which is equivalent to

n − deg(A_{j}) + 1 ≤ 2w_{j} ≤ n + deg(A_{j}) .

The claim follows immediately. □

A remark on expansion sequences Let again d ∈ ℕ. We see from the previous proposition that there are uncountably many sequences over 𝔽_{q} with d-almost perfect complexity profile. On the other hand, there are only countably many expansion sequences, even if one does not require that the degree of the function is 2. In contrast to this, in the conclusion of [20] it is conjectured that all sequences with almost perfect complexity profile are expansion sequences of functions of degree 2. We see that this conjecture fails in a dramatic way.

It is now natural to study sequences obtained with the construction in [20] via the theory of continued fraction expansion. The following proposition is classical.

Proposition 3 The following statements are equivalent:

a) a is an expansion sequence of a function f in a function field F with exact constant field 𝔽_{q} with respect to a place of degree 1 and a uniformizing parameter t of degree 2, where f ∉ 𝔽_{q}(t).

b) There exists a quadratic field extension F |𝔽_{q}(x) for which the place 𝔭_{∞} of 𝔽_{q}(x) is unramified and split into two places 𝔓_{1}, 𝔓_{2} of F and there exists a function f ∈ F − 𝔽_{q}(x) such that s is the expansion sequence of f at 𝔓_{1} with respect to the uniformizing parameter x^{−1}.

c) s is a root of an irreducible polynomial in 𝔽_{q}(x)[y] of degree 2 in y.

d) The continued fraction expansion of s is periodic.

In analogy to quadratic number fields, for a field k, a quadratic extension F |k(x) in which the place 𝔭_{∞} is unramified and split is often called a real quadratic function field. Note here that this might be seen as an abuse of terminology as a “real quadratic function field” is not a function field but an extension of the field 𝔽_{q}(x). Just as the theory of continued fractions for real quadratic number fields, the corresponding theory for real quadratic function fields over finite fields is well developed. A good overview over many aspects for odd characteristic is [19], the case of even characteristic is discussed in [21].

The theory of continued fraction can be used to obtain bounds on the degrees of the partial fractions A_{i}. We now discuss these results and relate them to Proposition 2.

Let now ay^{2} + by + c ∈ 𝔽_{q}[x, y] with a, b, c ∈ 𝔽_{q}[x] and a ≠ 0 be an irreducible polynomial. Let F be the extension of 𝔽_{q}(x) defined by the polynomial, and let f the residue class of y. We assume that 𝔭_{∞} is unramified and split in F; let 𝔓_{1} be one of these places. We consider the expansion s of f at 𝔓_{1} and the corresponding continued fraction expansion. We use the notations from above.

We note first that

deg(f) = max{deg(a), deg(b), deg(c)}

and therefore

deg(A_{i}) ≤ max{deg(a), deg(b), deg(c)}  (2)

for all i ∈ ℕ by the considerations of the previous section and Proposition 2. We now give potentially better bounds for i large enough.

The function g := af is a root of the monic polynomial y^{2} + by + ac, so af is integral over 𝔽_{q}[x]. Moreover, clearly, a divides ac which is the norm of g over 𝔽_{q}(x). We therefore have

f = \frac{g}{a}

with g integral, a ∈ 𝔽_{q}[x] and a|N(g). We are now in the situation which is considered in continued fraction expansions.

We make a case distinction according to whether the characteristic is odd or even.

We first consider the “classical” case that the characteristic is odd. We have the discriminant Δ = b^{2} − 4ac. From Proposition 3.2 (c) of [19] we learn that |A_{i}| ≤ |\sqrt{Δ}|, that is, |A_{i}|^{2} ≤ |Δ|, for i large enough. In other words:

deg(A_{i}) ≤ \frac{deg(Δ)}{2}

for i large enough. This inequality is always at least as strong as inequality (2). By the proof of Proposition 2, we have

n − \frac{deg(Δ)}{2} + 1 ≤ 2L_{n}(a) ≤ n + \frac{deg(Δ)}{2}

for n large enough.

Let now the characteristic be even. Then by Section 3 of [21] we have |A_{i}| ≤ |b|, that is,

deg(A_{i}) ≤ deg(b)

for i large enough. (In the introduction to [21] there are some assumptions on the minimal polynomial of g (in our notation), but these assumptions are not relevant for Section 3 of [21].) We thus have

n − deg(b) + 1 ≤ 2L_{n}(a) ≤ n + deg(b)

for n large enough.

4 Defining polynomials

Let an expansion sequence a over 𝔽_{q} defined by some function field F with exact constant field 𝔽_{q} a place 𝔓 of degree 1 and a uniformizing parameter t be given. Note here that we make no assumption on the degree of t.

Convention Let us assume that 𝔽_{q}(t, f) is a proper subfield of F. Let now 𝔓′ be the restriction of 𝔓 to 𝔽_{q}(t, f). Then 𝔓′ is also a place of degree 1, and the series of f defined by 𝔓 and the local parameter t is identical to the one defined by 𝔓′ and the local parameter t. So, in our study of expansion sequences, we can restrict our attention to sequence arising as above with F = 𝔽_{q}(t, f), and we do so in the following.

The elements t and f are algebraically dependent over 𝔽_{q}. So there exists a non-trivial polynomial h = h(t, y) ∈ 𝔽_{q}[t, y] with

h(t, f) = 0 .  (3)

Equation (3) is equivalent to

h(t, ∑_{i∈ℕ} a_{i}t^{i}) = 0 ,  (4)

so we have a non-trivial polynomial h which satisfies the latter condition. Let now I be the ideal of polynomials h ∈ 𝔽_{q}[t, y] with h(t, f) = 0.

The ideal I is the kernel of the homomorphism

𝔽_{q}[t, y] ⟶ F , t ↦ t , y ↦ f  (5)

and also of the homomorphism

𝔽_{q}[t, y] ⟶ 𝔽_{q}[[t]] , t ↦ t , y ↦ ∑_{i∈ℕ} a_{i}t^{i} .  (6)

Note that the latter fact implies that I is canonically attached to the sequence a.

The ideal I is a prime ideal and V (I) is a (possibly singular) plane affine curve with function field F. As V (I) is one-dimensional, by Krull’s Hauptidealsatz I is generated by a single irreducible polynomial. As usual, we call such a polynomial a defining polynomial of the curve V (I). Such a polynomial is unique up to a constant.

Let us consider the situation from the point of view of projective geometry: Let for this C be the complete non-singular curve over 𝔽_{q} corresponding to F, where we fix an isomorphism of function fields 𝔽_{q}(C) ≃ F. The place 𝔓 corresponds to an 𝔽_{q}-rational point of C which we denote by P. Let now h_{0}(t, y) be a defining polynomial of V (I), and let H_{0}(T, Y, Z) ∈ 𝔽_{q}[T, Y, Z] be the homogenization of h_{0}. Let

D_{0} := sup{− div(t), − div(f), 1} = sup{(t)_{∞}, (f)_{∞}} ,  (7)

where for some function g ∈ F^{∗}, (g)_{∞} is the pole divisor of g. Clearly, deg(D_{0}) ≤ deg(t) + deg(f). By definition, t, f, 1 generate O(D_{0}). Thus O(D_{0}) and the global sections t, f, 1 of O(D_{0}) define a morphism C ⟶ ℙ_{𝔽_{q}}^{2} which is given on an open subset U of C by Q ↦ (t(Q) : f(Q) : 1) for Q ∈ U(\overline{𝔽}_{q}). (Every rational map from C to some projective space ℙ_{𝔽_{q}}^{n} over 𝔽_{q} can be extended to a morphism from C to ℙ_{𝔽_{q}}^{n}. Here we have the stronger condition that t, f, 1 as global sections of O(D_{0}) directly define a morphism. See Section II.7 of [8] for background information.)

As by assumption F = 𝔽_{q}(t, f), the morphism is birational onto its image. It follows that the image V (H_{0}) has degree deg(D_{0}). We have therefore

deg(h_{0}) = deg(H_{0}) = deg(D_{0}) ≤ deg(t) + deg(f) .  (8)

We now turn the situation around and just assume that we are given some sequence a over 𝔽_{q} for which a non-trivial polynomial h ∈ 𝔽_{q}[t, y] with h(t, ∑_{i∈ℕ} a_{i}t^{i}) = 0 exists. Then the polynomials h with this property define again a non-trivial proper ideal of 𝔽_{q}[t, y]; let I_{a} be this ideal. Just as above, let h_{0} be a polynomial of I_{a} of minimal degree. Clearly, h_{0} is irreducible.

Let F := 𝔽_{q}(t)[y]/(h_{0}) and f the residue class of y. Then we have the embedding F ⟶ 𝔽_{q}((t)) given by t ↦ t and f ↦ ∑_{i∈ℕ} a_{i}t^{i} over 𝔽_{q}. This embedding defines in a unique way a valuation v on F with v(t) = 1 and thus a place 𝔓 of F of degree 1. Moreover, the expansion of f at 𝔓 with respect to t is of course the power series ∑_{i∈ℕ} a_{i}t^{i}.

The ideal I_{a} is now by definition the kernel of the homomorphism in (5) and thus also the kernel of the homomorphism in (6). By the previous considerations we conclude that I_{a} is generated by h_{0}.

We have proven:

Proposition 4 The expansion sequences are exactly the sequences a for which a non-trivial polynomial h ∈ 𝔽_{q}[t, y] with h(t, ∑_{i∈ℕ} a_{i}t^{i}) = 0 exists. Furthermore, if such a polynomial exists, the ideal of such polynomials is generated by a single irreducible polynomial.

This leads to the following definition.

Definition Let a be an expansion sequence. We call the ideal I_{a} the defining ideal of a, any non-trivial element of I_{a} a defining polynomial of a and a generating element h_{0} of I_{a} a minimal defining polynomial of a. Finally, we call the degree of a minimal defining polynomial of a the degree of a (as an expansion sequence).

Note that a necessary condition that a polynomial h_{0} ∈ 𝔽_{q}[t, y] is a defining polynomial of any expansion sequence is that its constant term is trivial.

Let now h_{0} be an irreducible polynomial in 𝔽_{q}[t, y] with trivial constant term. As above, let F = 𝔽_{q}(t)[y]/(h_{0}), and let f be the residue class of y.

Now the expansion sequences with minimal defining polynomial h_{0} correspond bijectively to the places 𝔓 of F of degree 1 with t, f ≡ 0 mod 𝔓. From a geometric point of view, the situation is as follows: Let H_{0} be the homogenization of h_{0} and (C, φ) a non-singular curve C over 𝔽_{q} together with a birational morphism φ : C ⟶ V (H_{0}); this datum is unique up to unique isomorphism. Now the places 𝔓 of F of degree 1 with t, f ≡ 0 mod 𝔓 correspond in a unique way to points P ∈ C(𝔽_{q}) with φ(P) = [0 : 0 : 1].

By this geometric description, two facts are immediate:

First, there are at most deg(h_{0}) expansion sequences with minimal defining polynomial h_{0}.

Second, if V (h_{0}) is non-singular at (0, 0) then there is exactly one such sequence. Let now h_{0} = ∑_{i,j} c_{i,j}t^{i}y^{j}. Then h_{0} is singular at (0, 0) if and only if c_{1,0} = c_{0,1} = 0.

For the general case, we have the following proposition.

Lemma 5 An expansion sequence of degree d_{0} is uniquely determined by its defining polynomial and its initial sequence of length d_{0}^{2}.

Proof. We consider h_{0} as a polynomial in y. As t is a local parameter of 𝔓, the extension F |𝔽_{q}(t) is separable, and therefore h_{0} is a separable polynomial. Let h_{0} = ∑_{i=0}^{d} c_{i}(t) · y^{i} with c_{i}(t) ∈ 𝔽_{q}[t] and c_{d}(t) ≠ 0, let Δ be the discriminant of h_{0}, and let R be the resultant of h_{0} and h′_{0} = \frac{∂h_{0}}{∂y}. We have R = ±c_{d} Δ, R is a non-trivial polynomial in 𝔽_{q}[t] of degree at most d_{0}(2d_{0} − 1), and the discriminant Δ is a non-trivial polynomial in 𝔽_{q}[t] too.

Assume now that we have two distinct roots ρ, ρ̃ of h_{0} as a polynomial over 𝔽_{q}[[t]] with ρ ≡ ρ̃ mod t^{n+1} for some n. Then ρ − ρ̃ ≡ 0 mod t^{n+1}. Now (ρ − ρ̃)^{2} is a divisor of Δ. Therefore Δ ≡ 0 mod t^{2n+2}. We obtain that 2n + 2 ≤ d_{0}(2d_{0} − 1), and therefore n < d_{0}^{2}. □

So far, we have fixed the minimal defining polynomial. The minimal defining polynomial of an expansion sequence of degree d_{0} is however also uniquely determined by its initial sequence of degree d_{0}^{2}. The key statement is the following lemma. The proof of the lemma is an easy adaption of the proof of Lemma 2.2 in [1].

Lemma 6 Let a be an expansion sequence over 𝔽_{q} of degree d_{0}. Let h ∈ 𝔽_{q}[t, y] be a non-trivial polynomial such that with d := deg(h) and n := dd_{0} we have

h(t, ∑_{i=1}^{n} a_{i}t^{i}) ≡ 0 mod t^{n+1} .  (9)

Then h is a defining polynomial for a.

Proof. Let a be an expansion sequence defined by F, f, t, 𝔓, where these objects are as above. Let D_{0} be as in (7). Then h(t, f) ∈ L(d · D_{0}). If now h(t, f) is non-trivial then deg(h(t, f)) = deg(h(t, f)_{∞}) ≤ deg(h) · deg(D_{0}) = dd_{0}.

Let us assume that congruence (9) holds for some n ∈ ℕ. Then h(t, f) ≡ 0 mod 𝔓^{n+1}. Under the assumption that h(t, f) is non-trivial, we now have deg(h(t, f)) ≥ v_{P} (h(t, f)) ≥ n + 1.

If n ≥ dd_{0} this is a contradiction. Therefore, we then have h(t, f) = 0 and thus h(t, ∑_{i∈ℕ} a_{i}t^{i}) = 0. □

Together these two lemmata give the following result.

Proposition 7 An expansion sequence of degree d_{0} is uniquely determined by its initial sequence of length d_{0}^{2}.

5 Computations

We now discuss computational aspects.

Our main goal is here as follows: Given an initial sequence of length at least d_{0}^{2} of an expansion sequence a of degree d_{0}, we want to compute large initial sequences of a. For this, we proceed as follows: First, we compute a minimal defining polynomial. Then from the minimal defining polynomial and the initial sequence we compute the further coefficients of the expansion sequence.

At the end of the section we also discuss why the results also apply if a finite intermediate sequence is given. This case is particularly relevant for cryptanalytic applications.

Recovering the minimal defining polynomial

Lemma 6 immediately gives rise to an algorithm to determine a minimal defining polynomial from a suitable initial sequence: Let some finite initial sequence of length at least d_{0}^{2} of an expansion sequence of degree d_{0} be given. The degree d_{0} itself need not be known a priori.

For d = 1, 2, …, we make an ansatz for h_{0} as a polynomial of degree d with unknown coefficients. Then (9) with n = d^{2} gives d^{2} homogeneous linear equations on the coefficients of h. We solve this system of equations by linear algebra. If we have found a non-trivial solution, we compute the corresponding polynomial. This is then a minimal defining polynomial.

Note that the number of monomials in 𝔽_{q}[t, y] of degree at most d is \binom{d+2}{2}. Thus a particular system to be solved has size d^{2} × \binom{d+2}{2}. We therefore obtain the following proposition.

Proposition 8 A minimal defining polynomial of an expansion sequence of degree d_{0} can be computed in polynomial time in d_{0} · log(q) from an initial sequence of length d_{0}^{2} or more.

We remark that in practice, one might try to apply this idea with n at least \binom{d+2}{2} but smaller than d^{2}.

Approaches to compute initial sequences

Let us now assume that we are given an initial sequence of length n ≥ d_{0}^{2} and a minimal defining polynomial h_{0} of an expansion sequence a of degree d_{0}. We wish to compute efficiently further coefficients of the sequence a. Three approaches to this problem come to mind:

1. A direct approach. For some m > n, we use the congruence h_{0}(t, ∑_{i=1}^{m} a_{i}t^{i}) ≡ 0 mod t^{m+1} to obtain a system of equations for the unknowns a_{n+1}, …, a_{m}. We then solve this system.

2. Expansions of functions with a function field theoretic approach. Let F := 𝔽_{q}[t, y]/(h_{0}), and let f be the residue class of y. Now every place 𝔓 of F of degree 1 with t, y ≡ 0 mod 𝔓 determines uniquely an expansion sequence of F, and one of these is ∑_{i∈ℕ} a_{i}t^{i}. By (5), the series a determines a unique place. We therefore have the following approach: First we determine all places 𝔓 with t, y ≡ 0 mod 𝔓. For each such place 𝔓, we compute the expansion of f at 𝔓 to the power d_{0}^{2}. From this, we determine which place is the correct one. Then we compute further coefficients as desired.

3. Hensel’s Lemma. We use a non-archimedean variant of Newton’s iteration or – with other words – we use some effective version of Hensel’s Lemma.

The use of Hensel’s Lemma (as formulated in [11]) to compute expansion sequences was already suggested in [10] for the case that t has degree 2. It is extremely efficient. However, in order that it can be applied, the initial sequence has to satisfy a condition (see condition (13) below). This condition are missing in [10].

Because Hensel’s Lemma cannot always be applied and also because of independent interest, we now first discuss the function field theoretic approach. Then we come to Hensel’s Lemma and give a criterion under which (11) is satisfied. The direct approach is not discussed in the following.

Let us for the following fix a definition:

Definition Let ∑_{i∈ℕ_{0}} a_{i}t^{i} ∈ 𝔽_{q}[[t]] and n ∈ ℕ_{0}. Then we call the polynomial ∑_{i=0}^{n} a_{i}t^{i} the initial series of ∑_{i∈ℕ_{0}} a_{i}t^{i} of length n.

Expansions of functions

We consider the general problem to compute an initial series of an expansion series of a function in a function field with respect to a place of degree 1 and a local parameter. For concreteness we only consider function fields over finite fields.

A first problem is how to represent the objects for computational purposes, most importantly the place of degree 1.

There are several approaches here, but one approach has proven itself to be particularly successful. The general idea of this approach is to adapt ideas which are successfully used for number fields. This approach has in particular been popularized by F. Hess in his work [9]. It is also implemented in the computer algebra system MAGMA ([2]). We describe this approach briefly. Besides [9], more information on this approach can be found in [6], and even more information, including proofs of all the following claims can be found in Chapter 2 of [5].

Let F/𝔽_{q} be a function field, and let C be a non-singular proper curve over 𝔽_{q} with a fixed isomorphism 𝔽_{q}(C) ≃ F. (As we do not assume that 𝔽_{q} is the exact constant field of F here, the curve C need not be geometrically irreducible.) The field F itself shall be given by an irreducible polynomial h_{0} ∈ 𝔽_{q}[t, y] which is separable in y. (C is then birational to V (h_{0}).) We consider the separable field extension F |𝔽_{q}(t). We have the “finite” order, which is the closure of 𝔽_{q}[t] in F and the “infinite” order, which is the closure of 𝔽_{q}[\frac{1}{t}]_{( \frac{1}{t})} in F. Bases of the orders over the base rings 𝔽_{q}[t] respectively 𝔽_{q}[\frac{1}{t}]_{( \frac{1}{t})} can be computed in polynomial time in deg(h_{0}) · log(q). Now a divisor on C is represented by a pair of two fractional ideals – one fractional ideal for each order. The fractional ideals themselves are also represented by bases over the base rings 𝔽_{q}[t] respectively 𝔽_{q}[\frac{1}{t}]_{( \frac{1}{t})}. Basic arithmetic can now be performed just as for ideals in number fields and as described for example in [3]. Furthermore, as shown in [9], there is an easy algorithm to compute, for a given divisor D of C, the Riemann-Roch space L(D). With appropriate representations of the objects involved (which we have not described in all details), divisor arithmetic and the computation of the Riemann-Roch spaces can be performed in polynomial time in deg(h_{0}), log(q) and the degrees of the divisors involved.

We now come to our application. Let an irreducible polynomial h_{0} ∈ 𝔽_{q}[t, y] which is separable in y be given. Let F := 𝔽_{q}[t, y]/(h_{0}). We are interested in the places 𝔓 of F of degree 1 with t, y ≡ 0 mod 𝔓. Let D := min{(t)_{0}, (y)_{0}}. Then the places we search for are exactly the places of degree 1 in the support of D. Now, D can be computed in polynomial time in deg(h_{0}) · log(q). The factorization of D as a formal sum of prime divisors (the so-called “free representation” of D) can be computed in an expected time which is polynomially bounded in deg(h_{0}) · log(q). (Here we have to factor polynomials, so this part of the algorithm is randomized.) From this factorization, the desired places can be read off.

At this point, we are left with the task to compute an initial part of an expansion series at a place of degree 1 with respect to the local parameter t. We consider this from a more general point of view.

We consider the general situation described above. So let again F be a function field over 𝔽_{q}, which is now given by some irreducible polynomial h_{0} ∈ 𝔽_{q}[t, y] which is separable in y. Let C be a complete non-singular curve with a fixed isomorphism F ≃ 𝔽_{q}(C). Furthermore, let 𝔓 be a place of degree 1 of F with local parameter t. Let P ∈ C(𝔽_{q}) be the point corresponding to the place 𝔓.

Let now f_{i} for i ∈ ℕ_{0} be inductively defined as follows:

f_{0} := f , f_{i+1} := \frac{f_{i} − f_{i}(P)}{t}  (10)

Then the expansion sequence of f at 𝔓 with respect to t is ∑_{i=1}^{∞} a_{i}t^{i} with a_{i} = f_{i}(P).

So we only have to consider one algorithmic problem: How can one efficiently evaluate a function at an 𝔽_{q}-rational point? That is, given F, f and P, how can one compute f(P)?

Let us first mention that this problem is not completely trivial for various reasons. One reason is that the point is not given by t and y-coordinates but as an ideal in an order of F. But let us now assume that we know the coordinates t(P), y(P). If then f is given by a polynomial in 𝔽_{q}[t, y], it is trivial to evaluate f at P. If however f is given as a fraction of polynomials or a sum of fractions of polynomials, it is not a priori clear now to perform the evaluation in complete generality.

There is however an easy solution via Riemann-Roch spaces: Note first that f(P) is the unique element a ∈ 𝔽_{q} such that f − a vanishes at 𝔓. All functions f − a lie in L((f)_{∞}), and they lie in L((f)_{∞} − P) if and only if a = f(P).

So we first compute a basis b_{1}, …, b_{ℓ} of the space L((f)_{∞} − P). Then 1, b_{1}, …, b_{ℓ} is a basis of L((f)_{∞}). We determine a, a_{1}, …, a_{ℓ} ∈ 𝔽_{q} with f = a + a_{1}b_{1} + ⋯ + a_{ℓ}b_{ℓ} with a linear algebra computation. Then f − a ∈ L((f)_{∞} − P) and therefore f(P) = a. This computation can be performed in polynomial time in deg(f) · deg(h_{0}) · log(q).

Now f_{k} lies in L((f)_{∞} + k · (t)_{∞}) and therefore deg(f_{k}) ≤ deg(f) + k · deg(t) ≤ (k + 1) · deg(h_{0}). It follows that the computation of the initial series ∑_{i=1}^{n} a_{i}t^{i} can be performed in polynomial time in n · deg(h_{0}) · log(q).

Let us now return to our initial problem, the computation of an sequence of a particular length n from an initial sequence of length d_{0}^{2}, where d_{0} is the degree of the expansion sequence.

We have to consider expansions with respect to t at all 𝔽_{q}-rational points P of C with (t(P), y(P)) = (0, 0). There are ≤ d_{0} such points. Therefore, the computation can be performed in polynomial time in n · d_{0} · log(q).

Hensel’s Lemma

The computation via Hensel’s Lemma is particularly efficient – provided that it is possible.

The following lemma and proposition are crucial.

Lemma 9 Let R be a complete discrete valuation ring with normalized valuation v, and let t be a local parameter. Let g ∈ R[y], and let r ∈ R be such that v(g(r)) > 2v(g′(r)). Let

r̃:= r − \frac{g(r)}{g′(r)} .

Then

v(g′(r̃)) = v(g′(r)) , v(g(r̃)) − 2v(g′(r̃)) ≥ 2(v(g(r)) − 2v(g′(r))) .

This lemma is proven in the course of the proof of Proposition 2 in Section II.2 of [11]. The next proposition follows easily.

Proposition 10 Let R be a complete discrete valuation ring with normalized valuation v, and let t be a local parameter. Let g ∈ R[y], and let r_{0} ∈ R be such that

v(g(r_{0})) > 2v(g′(r_{0})) .  (11)

Let b := v(g(r_{0})) − 2v(g′(r_{0})). Now let (r_{k})_{k∈ℕ} be a sequence in R such that for k ∈ ℕ_{0}

r_{k+1} ≡ r_{k} − \frac{g(r_{k})}{g′(r_{k})} mod t^{2^{k+1}b+2v(g′(r_{0}))} .  (12)

Then

v(g′(r_{k})) = v(g′(r_{0})) , v(g(r_{k})) − 2v(g′(r_{k})) ≥ 2^{k} · b ,
r_{k+1} ≡ r_{k} mod t^{b·2^{k}+v(g′(r_{0}))} , g(r_{k}) ≡ 0 mod t^{b·2^{k}+2v(g′(r_{0}))}

for all k ∈ ℕ_{0}. In particular, (r_{k})_{k∈ℕ_{0}} converges to a root ρ of g with ρ ≡ r_{0} mod t^{v(g(r_{0}))−v(g′(r_{0}))} and, more generally, ρ ≡ r_{k} mod t^{b·2^{k}+v(g′(r_{0}))}. Moreover, ρ is the unique root of g with ρ ≡ r_{0} mod t^{v(g′(r_{0}))+1} (and thus in particular with ρ ≡ r_{0} mod t^{v(g(r_{0}))−v(g′(r_{0}))}).

The proposition is one of the various statements which might be called “Hensel’s Lemma”. It is closely related to Proposition 2 in Section II.2 of [11]. However, we only require that the congruence (12) is satisfied. In contrast in Section II.2 of [11] an equality in R is demanded.

For the proof, note first that the congruence in the conclusion (except the uniqueness) follow immediately from the first two statements and (12).

The statements for arbitrary k follow immediately by induction from the lemma. The induction base k = 0 is trivial. So let us assume that the statements hold for a particular natural number k. Let r̃_{k+1} := r_{k} − \frac{g(r_{k})}{g′(r_{k})}. Then by the lemma applied with r_{k} and r̃_{k+1} we obtain that v(g′(r̃_{k+1})) = v(g′(r_{k})) = v(g′(r_{0})) and v(g(r̃_{k+1})) − 2v(g′(r̃_{k+1})) ≥ 2(v(g(r_{k})) − 2v(g′(r_{k}))) ≥ 2^{k+1}b, that is, v(g(r̃_{k+1})) ≥ 2^{k+1}b + 2v(g′(r_{0})). As r_{k+1} ≡ r̃_{k+1} mod t^{2^{k+1}b+2v(g′(r_{0}))} it follows that v(g(r_{k+1})) ≥ 2^{k+1}b + 2v(g(r_{0})) and v(g′(r_{k})) = v(g′(r̃_{k})) = v(g′(r_{0})).

The uniqueness is essentially stated in Proposition 4.1.37 of [4]. For the convenience of the reader, we recall the easy proof here:

Let us assume that there are two distinct roots ρ_{1}, ρ_{2} ∈ R of g with ρ_{1} ≡ ρ_{2} ≡ r_{0} mod t^{v(g′(r_{0}))+1}. By Gauß’ Lemma we have g = (y−ρ_{1})(y−ρ_{2})h with some h ∈ R[y]. This gives g′(ρ_{1}) = (ρ_{1} − ρ_{2})h(ρ_{1}) and therefore v(g′(r_{0})) = v(g′(ρ_{1})) ≥ v(ρ_{1} − ρ_{2}), that is, ρ_{1} ≢ ρ_{2} mod t^{v(g′(r_{0}))+1}, a contradiction. □

Just as previously, let h_{0} ∈ 𝔽_{q}[t, y] be an irreducible polynomial, let F := 𝔽_{q}[t, y]/(h_{0}), and let f be the residue class of y. We which to apply the above “Hensel’s Lemma” with R = 𝔽_{q}[[t]], v the corresponding normalized valuation, g = h_{0} and r_{0} = ∑_{i=1}^{n} a_{i}t^{i} for some initial sequence (a_{1}, …, a_{n}).

We now address the task to find a suitable condition under which

v(h_{0}(r_{0})) > 2v(\frac{∂h_{0}}{∂y} (r_{0}))  (13)

holds.

Note first that the condition is satisfied if \frac{∂h_{0}}{∂y} (r_{0}) ≠ 0. We now consider the general case.

Proposition 11 Let a be an expansion sequence of degree d_{0} with minimal defining polynomial h_{0} = ∑_{i=0}^{d} c_{i}(t)y^{i}, and let n ≥ 2d_{0}^{3}. Then r_{0} := ∑_{i=1}^{n} a_{i}t^{i} fulfills the condition v(h_{0}(r_{0})) > 2v(\frac{∂h_{0}}{∂y} (r_{0})).

Proof. Let Z be the splitting field of h_{0} ∈ 𝔽_{q}(t)[y] over 𝔽_{q}(t). We fix an embedding F ↪ Z, and we prolong the valuation v to Z. We denote the resulting valuation again by v.

Let h_{0} = c · ∏_{j=1}^{m}(y − f_{j}) ∈ Z[y], where c ∈ 𝔽_{q}[t] and f_{1} = f. By Gauß’ Lemma, v(f_{j}) ≥ 0 for all j. Furthermore v(h_{0}(r_{0})) ≥ v(c) + v(r_{0} − f) ≥ v(c) + n + 1 ≥ n + 1. With an easy adaption of the proof of Lemma 5 we have for j > 1 v(f − f_{j}) ≤ d_{0}^{2} and thus v(r_{0} − f_{j}) ≤ d_{0}^{2} too.

We have \frac{∂h_{0}}{∂y} (r_{0}) = c · ∑_{ℓ=1}^{m} ∏_{j≠ℓ}(y − f_{j}). Now for ℓ > 1, v(∏_{j≠ℓ}(r_{0} − f_{j})) ≥ v(r_{0} − f) ≥ n + 1. Furthermore v(∏_{j>1}(r_{0} − f_{j})) ≤ (m − 1) · d_{0}^{2} ≤ d_{0}^{3} − d_{0}^{2}. Therefore v(\frac{∂h_{0}}{∂y} (r_{0})) ≤ v(c) + d_{0}^{3} − d_{0}^{2} ≤ d_{0}^{3} and 2\frac{∂h_{0}}{∂y} (r_{0}) ≤ 2d_{0}^{3} < n + 1 ≤ v(h_{0}(r_{0})). □

The computation is in principle straightforward: Let an irreducible polynomial h_{0} such that (13) holds and a finite sequence (a_{1}, …, a_{n}) be given. Let us assume that (13) holds with r_{0} := ∑_{i=1}^{n} a_{i}t^{i}.

We apply Hensel’s Lemma with g := h_{0}. As above, let b := v(g(r_{0})) − 2v(g′(r_{0})). In the k-th iteration, we compute the unique polynomial of minimal degree r_{k+1} for which (12) holds. The computation takes place inside the residue class ring 𝔽_{q}[t]/(t^{2^{k+1}b+2v(g′(r_{0}))}).

Note that this computation is very efficient because we essentially double the length of the computed initial sequence at every iteration. One can now combine this method with fast arithmetic. Like this, one obtains:

Proposition 12 There exists a Turing machine with the following specification: Upon input of an irreducible polynomial h_{0} such that (13) holds and a finite initial sequence (a_{1}, …, a_{n}) for which (13) holds the machine never terminates and it outputs the coefficients of an expansion sequence with minimal defining polynomial h_{0} and initial sequence (a_{1}, …, a_{n}). Moreover, the running time until the m^{th} coefficient is output is in Õ(m · deg(h_{0})).

Storage requirements

With the two methods discussed above and also with the “direct approach” mentioned above, the storage requirements are enormous: In order to compute a_{n+1}, the complete initial sequence (a_{1}, …, a_{n}) has to be stored. It is an interesting question if there is any method to compute entries of a which uses less storage.

For the time being, the storage requirements put serious constraints on the use of expansion sequences for stream ciphers – independently of our attack.

Finite intermediate sequences

We now consider a variant of the above. In cryptanalytic applications, it is unlikely that one has access to an initial sequence. It is more realistic to assume that one has access to a finite subsequence (a_{k+1}, …, a_{k+m}) of an expansion sequence a.

Let a be given by F, 𝔓, t, f as above, and furthermore let f_{k} be defined as in (10). Then the sequence (a_{k+i})_{i∈ℕ} is the expansion sequence of t · f_{k+1} with respect to t at 𝔓. So all the above considerations hold when applied to this sequence.

Let now d_{k} be the degree of this expansion sequence. (This generalizes the definition of d_{0} given above.) As t · f_{k+1} ∈ L((f)_{∞} + k · (t)_{∞}), we have

d_{k} ≤ deg(f) + k · deg(t) .

In terms of d_{0}, we have

d_{k} ≤ (k + 1) · d_{0} .

The dependence on k is surely a weakness of the attack. We remark however again that for any of the three methods mentioned above, for the generation of some element a_{n+1}, the complete initial sequence (a_{1}, …, a_{n}) has to be computed and stored.

6 Outlook and comments

We have seen that expansion sequences should be regarded as cryptographically weak. It is now natural to define a new notion of complexity of sequences over 𝔽_{q}:

For a finite sequence a of length n we define the expansion complexity, E_{a}, as the minimum of the degrees of non-trivial polynomials h(t, y) ∈ 𝔽_{q}[t, y] with h(t, ∑_{i=1}^{n} a_{i}t^{i}) = 0 mod t^{n+1}. Clearly, we always have E_{a} ≤ L_{a}. We define the expansion complexity profile of a finite or infinite sequence a of length m as (E_{a}(n))_{n=1}^{m}, where E_{a}(n) is the expansion complexity of the initial sequence of length n of a. We remark that for a given sequence, one should not only consider the expansion complexity profile of the sequence but in fact all expansion complexity profiles for arbitrary starting points (that is, for the corresponding left-shifted sequences). In the realm of linear complexity, the corresponding suggestion was already made in [17], and a first study in this direction is [12].

The new notion of expansion complexity leads to some new research directions. One interesting task is to develop a probabilistic theory of expansion complexity, just as a probabilistic theory of linear complexity has been developed in [13] and [15]. A first task is here to study the probability distributions of expansion complexities for uniformly randomly distributed sequences of a fixed length.

After such a theory has been developed, pseudorandom generators for cipher streams should be analyzed from a statistic point of view via the theory. Let us note here that a corresponding statistic program for linear complexity is part of a test suite, issued by NIST, for pseudorandom sequences for cryptographic use ([7]).

Finally, we would like to make a remark on terminology: In [18], [14] and various other works, the authors speak of “sequences with perfect linear complexity profile”. In the beginning of [20] the authors speak of sequences with “perfect linear complexity profile” or with “almost perfect linear complexity profile”. However, later in this work and also in [16], the authors speak of “(almost) perfect” sequences instead. Moreover, sequences with d-almost perfect complexity profile are called “d-perfect”. Here we would like to make the following remark: The previous expressions are completely adequate. However, the newer expressions are questionable. It is one thing to express that a mathematical object is “(almost) perfect” with respect to a particular aspect under consideration. It is however something else to say that a mathematical object is “(almost) perfect” by itself. Concretely, having in mind the results of this work, we would like to suggest to return to the older terminology and to discontinue speaking of “(almost) perfect sequences” and of “d-perfect sequences”. Consequently, we have avoided the usage of the expressions “(almost) perfect sequence” and “d-perfect sequence” in this article.

References

[1] M. Baker, E. González-Jiménez, J. González, and B. Poonen. Finiteness results for modular curves of genus at least 2. Amer. J. Math., 127, 2005.

[2] W. Bosma, J. Cannon, C. Fieker, and A. Steel, editors. Handbook of Magma functions, Edition 2.17. 2011.

[3] H. Cohen. A Course in Computational Algebraic Number Theory. Springer-Verlag, 1996.

[4] H. Cohen. Number Theory – Volume 1: Tools and Diophantine Equations. Springer-Verlag, 2007.

[5] C. Diem. On arithmetic and the discrete logarithm problem in class groups of curves, 2008. Habilitation thesis.

[6] C. Diem. On the discrete logarithm problem in class groups of curves. Math. Comp., 80:443 – 475, 2011.

[7] A. Rukhin et al. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST Special Publication 800-22, 2010.

[8] R. Hartshorne. Algebraic Geometry. Springer, 1977.

[9] F. Heß. Computing Riemann-Roch spaces in algebraic function fields and related topics. J. Symb. Comput., 11, 2001.

[10] D. Kohel, S. Ling, and C. Xing. Explicit sequence expansions. In Sequences and their Applications – Proceedings of SETA ’98, Discrete Mathematics and Theoretical Computer Science. Springer, 1999.

[11] S. Lang. Algebraic Number Theory. Springer-Verlag, 1994.

[12] H. Niederreiter. Keystream squences with a good linear complexity profile for every starting point. In J.-J. Quisquater and J. Vandewalle, editors, Advances in Cryptology – Eurocrypt ’89, volume 434 of LNCS, pages 523 – 532. Springer-Verlag.

[13] H. Niederreiter. The probabilistic theory of linear complexity. In C. Günter, editor, Advances in Cryptology – Eurocrypt ’88, volume 330 of LNCS, pages 191–209. Springer-Verlag, 1988.

[14] H. Niederreiter. Sequences with almost perfect linear complexity profile. In D. Chaum and W. Price, editors, Advances in Cryptology – Eurocrypt ’87, volume 330 of LNCS, pages 37 – 51. Springer-Verlag, 1988.

[15] H. Niederreiter. A combinatorial approach to probabilistic results on the linear complexity profile ofrandom sequences. J. Cryptology, pages 105–112, 1990.

[16] H. Niederreiter and C. Xing. Rational Points on Curves over Finite Fields. Cambridge University Press, 2001.

[17] F. Piper. Stream ciphers. Elektrotechnik und Maschinenbau, 104:564 – 568, 1987.

[18] R. Rueppel. Analysis and Design of Stream Ciphers. Springer-Verlag, Berlin, 1986.

[19] A. Stein. Explicit infrastructure for real quadratic function fields and real hyperelliptic curves. Grasnik Mathematicki, 44:89 – 126, 2009.

[20] C. Xing and K. Lam. Sequences with almost perfect linear complexity profiles and curves over finite fields. IEEE Trans. Infor. Theory, pages 1267–1270, 1999.

[21] R. Zuccherato. The continued fraction algorithm and regulator for quadratic function fields of quaracteristic 2. J. Algebra, 563 – 587, 1997.

Claus Diem University of Leipzig Mathematical Institute Johannisgasse 26 04103 Leipzig Germany diem@math.uni-leipzig.de