CR 2

Some Applications of Coding
Theory in Cryptography
ii
CIP-DATA LIBRARY TECHNISCHE UNIVERSITEIT EINDHOVEN
Doumen, Jeroen M.
Some applications of coding theory in cryptography / by Jeroen M.

Doumen. – Eindhoven : Technische Universiteit Eindhoven, 2003.
Proefschrift. – ISBN 90-386-0702-4
NUR 919
Subject headings : cryptology / coding theory / prime numbers
2000 Mathematics Subject Classification : 94A60, 11T71, 11A41
Printed by Eindhoven University Press.

Cover by JWL Producties.
Kindly supported by STW.
Some Applications of Coding Theory in Cryptography
proefschrift
ter verkrijging van de graad van doctor aan de

Technische Universiteit Eindhoven, op gezag van de
Rector Magnificus, prof.dr. R.A. van Santen, voor een
commissie aangewezen door het College voor
Promoties in het openbaar te verdedigen
op 6 juni 2003 om 16.00 uur
door
Jeroen Mathias Doumen
geboren te Warstein, Duitsland.

Dit proefschrift is goedgekeurd door de promotoren:
prof.dr.ir. H.C.A. van Tilborg

en
prof.dr. A.K. Lenstra
Contents
Contents v
Preface vii
1 Preliminaries and notation 1

1.1 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Coding Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Goppa codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 The Maximal Error Property . . . . . . . . . . . . . . . . . . 6
2 Adaptive chosen ciphertext attacks on the McEliece cryptosystem 9

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 The McEliece Public–Key Cryptosystem . . . . . . . . . . . . . . . . 11
2.3 An adaptive chosen ciphertext attack . . . . . . . . . . . . . . . . . . 12
2.4 Countermeasures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Digital signature schemes based on error–correcting codes 21

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Security analysis of the Xinmei scheme . . . . . . . . . . . . . . . . . 23
3.2.1 Description of the Xinmei scheme . . . . . . . . . . . . . . . . 23
3.2.2 Some weaknesses in the Xinmei scheme . . . . . . . . . . . . 24
3.3 The Alabbadi–Wicker scheme . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Modifying the Alabbadi–Wicker scheme . . . . . . . . . . . . . . . . 28
3.5 Cryptanalysis of the Alabbadi–Wicker scheme . . . . . . . . . . . . . 29
3.5.1 Resistance of the Alabbadi–Wicker scheme against attacks . . 29
3.5.2 A universal forgery of the Alabbadi–Wicker scheme . . . . . . 30
3.5.3 Cryptanalyzing the modified Alabbadi–Wicker scheme . . . . 34
3.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Two families of Mersenne–like primes 37

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Testing for primality . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
v
vi CONTENTS
4.3 Prime-generating elliptic curves . . . . . . . . . . . . . . . . . . . . . 39

4.4 A primality test for certain elliptic curves . . . . . . . . . . . . . . . 41
4.5 The Wagstaff conjecture . . . . . . . . . . . . . . . . . . . . . . . . . 45
5 Pseudorandom sequences from elliptic curves 49

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2 Some properties of elliptic curves . . . . . . . . . . . . . . . . . . . . 49
5.3 Pseudorandom sequences . . . . . . . . . . . . . . . . . . . . . . . . 51
5.4 Using additive characters . . . . . . . . . . . . . . . . . . . . . . . . 53
5.5 Using multiplicative characters . . . . . . . . . . . . . . . . . . . . . 58
5.6 Using linear recurrence relations on elliptic curves . . . . . . . . . . 63
5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Bibliography 67
Index 73
Acknowledgements 75
Samenvatting 77
Curriculum Vitae 79
Preface
Nowadays, many people claim we live in the so-called information age. Clearly, the
rise of the internet (among others) has made information available to people on an
unprecedented scale and in a magnitude never seen before so widely. This can and
has been compared to the introduction of the printing press in the Middle Ages.
With its advent, the massive distribution of books and ideas became possible, and
the printing press certainly has played a significant role since its invention. Even
while it is still much too early to tell, the rise of the internet seems to be of a similar
scale - for the first time in history, everyone is able to publish his own words.
However, such new flows of information need new technologies to expedite them.
Of course, the basic networks along which the information flows have to be built.
But there are other key issues here: one should be able to rely on the received
information, in the sense that it is received correctly, even when the underlying
network it is transmitted over is imperfect and thus prone to errors. Theoretical
work on this began in the late 1940’s with work of Shannon [Sha48] and Hamming
[Ham50]. This has grown to a new branch of mathematics, called coding theory.
Also, there are many cases in which (a form of) confidentiality is required. An
obvious example would be sending a love letter to one’s secret lover, or sending other
sensitive information in some digital form. But there are also other concerns: for
instance, one could want to be sure of whether a certain (electronic) letter actually
comes from the mentioned author. In daily life, the author can achieve this by
writing his signature on the letter. But how can one do that in an email? Another,
more mundane example is getting money from an ATM. Before handing you money,
the bank wants to be sure that there is enough money in your account. On the
other hand, you would like to be the only person able to withdraw money from
your account. Again, going to a bank teller and using handwritten signatures has
been the solution for centuries. But this is very difficult, if not impossible for an
automated machine, and so other, intrinsically digital methods must be adopted.
The tools of choice here, collectively called cryptography, used to protect national
secrets. An excellent work on this history is given in Kahn’s The Codebreakers
[Kah67]. From the second world war onward, this rapidly became less of an art
form and more and more a serious branch of mathematics.
Both coding theory and cryptography have been already proven to be essential
in our information age. While they may seem to achieve opposite goals at first sight,
they share much more than that. This thesis aims to reveal at least part of that
vii
viii PREFACE
relation: how coding theory can be applied in cryptography. In the first chapter, a
more detailed introduction to the objectives of cryptography will be given. Also, a
short description of the basics of coding theory will be given there.
In Chapter 2 attacks on the McEliece public–key cryptosystem are introduced
in which a malicious sender, or an adaptive eavesdropper, has a method available
to find out whether a ciphertext decrypts properly or not. From this information
she can then extract the plaintext that was encrypted. In this chapter it is shown
that the McEliece public–key cryptosystem is indeed susceptible to these kinds of
attacks and a detailed algorithm for such an attack is given and analyzed. Thus
care should be taken when implementing this scheme, and possible countermeasures
are discussed which thwart this attack.
Chapter 3 deals with the security of digital signature schemes based on error–
correcting codes. Several attacks against the Xinmei scheme, the first such scheme,
are surveyed and reasons for the failure of the Xinmei scheme are given. Another
weakness is found in another such scheme, proposed by Alabbadi and Wicker, which
leads to an attacker being able to forge signatures at will. Further analysis shows
that this new weakness also applies to the original Xinmei scheme.
Then, in Chapter 4, work of a more theoretical nature will be discussed. In
this chapter two families of numbers are introduced which can efficiently be tested
for primality. These families naturally extend the Mersenne numbers to the area of
elliptic curves. The first few primes in these families are also presented and compared
to the generalized Wagstaff conjecture. However, results from this chapter will turn
out to be useful in the last chapter.
Lastly, Chapter 5 will employ algebraic geometry to produce pseudorandom
sequences. Some known constructions to produce pseudorandom sequences with
the aid of elliptic curves will be generalized there. Both additive and multiplicative
characters on elliptic curves will be used for this purpose. Finally, the use of linear
recurrencies on elliptic curves will be studied.
Chapter 1
Preliminaries and notation
1.1 Cryptography
The aim of cryptography is to provide secure transmission of messages, in the

sense that two or more persons can communicate in a way that guarantees that the
desired subset of the following four primitives is met:
(i). Confidentiality. This primitive is usually perceived to be the main focus of
cryptography, providing a way such that the information can only be viewed
by those people authorized to see it.
(ii). Data integrity. This service will provide a means to check if the transmitted
information was altered in any way, including but not limited to things like
insertion, deletion and substitution of messages.
(iii). Authentication. This service will establish some identity pertaining to the
message. Thus, this primitive can (among others) be used to guarantee the
identity of the sender, guarantee the identity of the receiver, or guarantee the
time the message was sent.
(iv). Non-repudiation. This serves to prevent someone from denying previous com-
mitments. It is needed in cases where disputes might have to be resolved, for
instance in E-commerce.
While cryptography is often thought of as a tool to provide confidentiality, the
other three primitives are actually much more important in daily life.
In order to build cryptographic protocols supplying one or more of the above
primitives, some building blocks are needed. For instance, one often uses a one-way
function, of which the values should be easy to compute, but the inverse should
be impossible to compute for most values. In practice, one is often content with a
function for which it is computationally infeasible to compute inverses from. When
a one-way function is defined on arbitrary inputs (i.e. on bitstrings of arbitrary
length), it will be called a hash function. If a one-way function can be (efficiently)
inverted given some additional information, it is called a trapdoor one-way function.
1
2 Preliminaries and notation
In a cryptographic protocol, the users are often called Alice and Bob (instead of
A and B). An eavesdropper or adversary will be denoted by Eve. This terminology
will be used throughout this thesis. The initiator of the protocol will be called Alice
(so usually she will be the sender), and the intended recipient will be called Bob.
Cryptographic protocols include such things as encryption schemes, also called
cryptosystems, which aim to achieve confidentiality. A description of such a scheme,
called the McEliece cryptosystem, which is based on coding theory, will be given
in Section 2.2. Other well-known cryptosystems are, among others, DES [MOV97,
Section 7.4], AES [DR98], RSA [RSA78] (which can be used for digital signatures
as well) and Diffie-Hellman [DH82], which is used for key agreement. Other ex-
amples of cryptographic protocols include digital signature schemes, which try to
establish authentication and data integrity of a certain message. A history of sig-
nature schemes based on error–correcting codes will be given is Section 3.1. Others
include RSA [RSA78] and DSA [MOV97, Section 11.5]. For a more complete list
of cryptographic protocols, as well as descriptions of those only mentioned here, see
[MOV97].
1.2 Coding Theory

The aim of coding theory is to provide secure transmission of messages, in the
sense that (up to a certain number of) errors that occurred during the transmission
can be corrected. However, for this capability a price must be paid, in the form
of redundancy of the transmitted data. In this thesis only linear codes will be
considered.
First the alphabet Fq is chosen. In practice, this usually is the field of binary
numbers, but any prime power q is allowed. Let Fnq denote a n–dimensional vector
space over the finite field Fq . A linear [n, k] code C is a k–dimensional linear subspace
of Fnq . The elements of C are similarly called codewords. A generator matrix G for
C is a k × n (q–ary) matrix whose rows span C. This means that each codeword c
can be written as c = mG (in C) with m ∈ Fkq . One can formulate this by saying
that the message vector m is encoded in the codeword c. The quantity n − k is
the redundancy of C. It gives the number of excess symbols in c, compared to the
message vector m.
Now c is sent over an (unreliable) channel and certain errors may be inflicted
on c: the received vector is y = c + e where e is a so called error vector. Let
the Hamming weight wH (x) of a vector x simply count the number of non–zero
coordinates of x. If the weight of e is not too large, the received vector y coincides
on many coordinates with c and c can be recovered.
With a code C one can associate its dual code C ⊥ , which is the (n−k)–dimensional
subspace orthogonal to C. In other words, the dual code consists of all vectors of Fnq
that are orthogonal to all codewords of C. A generator matrix H of the dual code
C ⊥ is also called a parity check matrix of C, since it has the property that cH T = 0
for each codeword c ∈ C and vice versa.
1.2 Coding Theory 3
The (Hamming) distance dH (x, y) between vectors x and y is defined as the

number of coordinates where x and y differ. Note that dH (x, y) = wH (x − y).
The minimum distance d of a code C is defined as the minimum Hamming distance
between different codewords in C. Since C is linear, an equivalent definition would
be that d is the minimum non–zero weight of a codeword in C. A [n, k] code with
minimum distance d will be denoted as a [n, k, d] code. In general, determining
the minimum distance d of a certain code (given e.g. by a generator matrix) is
not an easy problem. However, some bounds on the minimum distance are known,
one of which is Singleton’s bound d ≤ n − k + 1. Let Aw denote the number of
codewords in C of Hamming weight w. The numbers A0 , A1 , . . . , An are called the
weight distribution of C.
The number t = b d−1 2 c is called the error–correcting capability of C. It follows
from the triangle inequality that for each element y in Fnq there can be at most one
element c in C at Hamming distance ≤ t to it. So, in principle, one can correct up
to t errors inflicted to an element in C by finding the nearest point in C. However, in
practice the process of determining the nearest point (called decoding) is often very
complex. To illustrate, the problem for general linear codes on deciding on whether
there exists a point in C at a given distance of a given point x ∈ Fnq is known to be
in the class NP–complete [BMT78]. Fortunately there are certain classes of linear
codes where decoding can be done quite effectively. As an example of this, Goppa
codes shall be defined and described in the next subsection. More information about
coding theory can for instance be found in [MS77; Til93a].
1.2.1 Goppa codes

In this subsection, a short introduction to Goppa codes will be given. For a
more detailed description, as well as for proofs of most (unproven) statements given
below, see [MS77, Section 12.3].
First, choose a Goppa parameter r, which will determine both the dimension
and the minimum distance of the code. Let G(x) be a polynomial of degree r over
the finite field Fqm and let Γ = {γ1 , γ2 , . . . , γn } contain n distinct members of Fqm
(n will be the length of the codewords) such that G(γi ) 6= 0 for all 1 ≤ i ≤ n. In
practice, the choice Γ = Fqm , together with an irreducible polynomial G(x) is often
made. The Goppa code CΓ generated by the Goppa polynomial G(x) consists of all
words c = (c1 , c2 , . . . , cn ) ∈ Fnq satisfying
n
X ci
≡0 (mod G(x)).
i=1
x − γi
Observe that the inverse of each polynomial x−γi exists modulo G(x), as G(γi ) 6=
0 for all 1 ≤ i ≤ n. The code CΓ is linear and of dimension k ≥ n−mr. Its minimum
distance d satisfies d ≥ r + 1. Moreover, if the characteristic of Fq is 2 and G(x)
does not have multiple zeros, then it even satisfies d ≥ 2r + 1. The usual form of
the parity check matrix of CΓ is given by
G(γ1 )−1 G(γn )−1

 
···
 γ1 G(γ1 )−1 ··· γn G(γn )−1 
γ12 G(γ1 )−1 γn2 G(γn )−1
 
HΓ = 
 ··· .

(1.1)
 .. .. 
 . . 
γ1r−1 G(γ1 )−1 · · · γnr−1 G(γn )−1
From this form, a parity check matrix over Fq can be obtained by writing each
entry as the corresponding column vector of length m from Fq .
An important feature of Goppa codes is the existence of an efficient decoding
algorithm At0 for any t0 less than or equal to the designed error–correcting capability
t. In practice, one therefore corrects up to the designed error–correcting capability.
Decoding can be done as follows: suppose that the vector y = (y1 , y2 , . . . , yn ) is
received. The syndrome polynomial Sy (x) of y is defined by
r−1
X r−1
X n
X
Sy (x) = xi (HΓ · yT )i+1 = xi γji yj G(γj )−1 ,
i=0 i=0 j=1
or equivalently
n
X yi
Sy (x) ≡ (mod G(x)).
i=1
x − γi
The syndrome polynomial Sy (x) is zero if and only if y ∈ CΓ . Now write y as
y = c + e, where c ∈ CΓ and wH (e) ≤ t. (1.2)

Let E be the set of non–zero coordinates of e = (e1 , e2 , . . . , en ). Then the error–
locator polynomial σ(x) and the error evaluator polynomial ω(x) are defined by
Y
σ(x) = (x − γi )
i∈E
and X Y
ω(x) = ei (x − γj ).
i∈E j∈E\{i}
Then deg ω(x) < deg σ(x) ≤ t, gcd(σ(x), ω(x)) = 1 and the following, so–called
key equation holds:
Sy (x)σ(x) ≡ ω(x) (mod G(x)). (1.3)
In order to decode the received word y, this equation has to be solved. Of course,
many solutions exist for this equation, and the one with the least degree of σ(x)
should be found. Such a solution certainly exists and is unique, since it was assumed
that at most t errors occurred.
1.2 Coding Theory 5
One way to do this is by using Euclid’s extended algorithm. On input of two

starting values r−1 (x) and r0 (x), this algorithm can be used in step i to calculate
Ui , Vi and ri satisfying
ri (x) = (−1)i (Ui (x)r0 (x) − Vi (x)r−1 (x)) ≡ (−1)i Ui (x)r0 (x) (mod r−1 (x)).
Now, starting with the values r−1 (x) = G(x) and r0 (x) = Sy (x), proceed until
one finds a rl (x) satisfying deg rl (x) ≤ 12 r − 1. Then σ(x) and ω(x) can be written
as
Uk (x)
σ(x) = (1.4)
Uk (0)
and
ω(x) = (−1)k Uk (0)Uk (x). (1.5)
These polynomials are proven to be the correct ones in [MS77]:
Proposition 1.2.1 ([MS77, Chapter 12, Theorem 16]) The polynomials σ(x)
and ω(x) given by Equations (1.4) and (1.5) are the unique solution to the Key
Equation (1.3) with σ(0) = 1, deg σ(x) ≤ 21 r, deg ω(x) ≤ 12 r − 1 and deg σ(x) as
small as possible.
Clearly, once σ(x) and ω(x) are determined, one can easily determine c and e.
The error locations set E is completely determined by the roots of σ(x). Further,
for each i in E one can compute the error value ei (the i–th coordinate of e) from
the relation ei = ω(γ i)
σ(γi ) . Finally, the original codeword c can be computed as c =
y − e. Note that for this algorithm to work, the parity check matrix must be in the
usual form (1.1), since the key equation only holds in that case. Also, the order of
coordinates {γi } in Fqm must be known, since otherwise the error vector e could not
be reconstructed from the error set E. Also note that this algorithm will correct up
to br/2c errors, regardless of the characteristic of Fq .
In order to correct up to r errors if the code is binary (i.e. if the characteristic
of Fq is 2) and if G(x) has no multiple zeroes, one has to slightly adapt the above
algorithm. First note that in this case the Key Equation (1.3) can be rewritten as
S(x)σ(x) ≡ σ 0 (x) (mod G(x)).
Splitting of the squares and the non-squares in σ(x), one can write σ(x) =
α2 (x) + xβ 2 (x), where deg β(x) < deg α(x) ≤ r/2. Thus the key equation can be
further rewritten as
β 2 (x) (xS(x) + 1) ≡ S(x)α2 (x) (mod G(x)).
Multiplying this equation by the inverse1 of S(x), one sees that β 2 (x)T (x) ≡ α2 (x)
(mod G(x)) for some polynomial T (x). Since the characteristic is 2, the Frobenius
1 If this inverse does not exist, G(x) is not irreducible. Then one can work modulo the irreducible
factors of G(x) and apply the Chinese Remainder Theorem. This is possible since G(x) has no
multiple zeroes.
map y 7→ y 2 is an automorphism, and thus is it possible and well-defined to take

the square root of an element of the field1 Fqm [x]/(G(x)). So there exists a unique
polynomial R(x) satisfying T (x) = R2 (x). Thus the key equation becomes
R(x)β(x) ≡ α(x) (mod G(x)).
On this form, Euclid’s extended algorithm can be applied as described earlier.
1.2.2 The Maximal Error Property

Now the following property of a decoding algorithm At shall be investigated.
This property will play a crucial role in Chapter 2.
Property 1.2.2 (Maximal Error Property ) On input of a vector y ∈ Fnq , the

decoding algorithm At will return a codeword c in C at distance ≤ t to y if such a
codeword exists. Otherwise, it will return an error–message.
Note that this property in fact states that the decoding algorithm At will not
try to correct t + 1 errors. This is not possible in general if t = b d−1
2 c. However,
even then it might be possible to correct t + 1 errors in a few isolated cases.
Proposition 1.2.3 states a property of the two main algorithms to determine the
pair σ(x), ω(x) satisfying the Key Equation (1.3). One of the main algorithms
is Euclid’s algorithm which was described in the previous subsection. The other
is the Berlekamp–Massey algorithm [MS77, Section 9.6], which tries to the pair
{σ(x), ω(x)} by solving a set of simultaneous linear equations, namely the general-
ized Newton identities [MS77, Theorem 24, Chapter 8] It is important to note that
the Berlekamp–Massey algorithm is successful if and only if Euclid’s algorithm is;
they also lead to the same result. This is irrespective of whether S(x) is an actual
syndrome polynomial Sy (x). The behavior of the Berlekamp–Massey algorithm and
Euclid’s algorithm with “bad” input, i.e. when inputting a syndrome polynomial of
a vector y at distance more than t from the code, is the same.
These two decoding algorithms for Goppa codes have the maximal error property:
Proposition 1.2.3 Let C be a Goppa code with designed error–correcting capability

t (so r = t in the binary case, and r = 2t otherwise), and let At be either Euclid’s
extended algorithm or the Berlekamp–Massey algorithm for decoding C. Then At
has the maximal error property.
Proof: First, suppose the characteristic of Fq is not equal to 2, suppose that

y ∈ Fnq is the input to At and suppose that At outputs a vector v in Fnq (so no
error–message is returned). As the implementation is not assumed to explicitly
check that the output is actually a codeword, v does not need to be a codeword.
Certainly, if y is of the form (1.2) then At will output c. However, to prove the
proposition the converse has to be shown, i.e. that equality holds in (1.2) with
c = v.
To this end, the decoding process is analyzed. First the decoding process tries
– using either Euclid’s or Berlekamp–Massey’s algorithm – to find two polynomials
1.2 Coding Theory 7
σy (x) and ωy (x) of the correct degrees and satisfying the Key Equation (1.3). If
this fails, an error–message is assumed to be returned. On the other hand, if σy (x)
and ωy (x) are determined, the decoding process determines the presumed set of
error locations E 0 = {1 ≤ i ≤ n|σy (γi ) = 0}. If E 0 has cardinality strictly less than
deg(σy (x)), an error–message is assumed to be given. Next, the decoding process
determines a vector e0 of weight at most t by
ωy (γi )/σy (γi ) if i ∈ E 0 ,

0
ei =
0 otherwise.
Note that all e0i with i ∈ E 0 are necessarily non–zero, as otherwise the σy and
ωy would not be relatively prime, and thus the degree of σy would not be minimal.
Finally, the decoding process determines v = y − e0 , which is returned by At .
Now to see that v is a member of C, we consider the polynomials σe0 (x) and
ωe0 (x) (corresponding to e0 written as e0 = 0 + e0 ), i.e. Se0 (x)σe0 (x) ≡ ωe0 (x)
(mod G(x)). First the observation is made that the pair (σe0 (x), ωe0 (x)) is equal
to the pair (σy (x), ωy (x)). That σy (x) = σe0 (x) is trivially true, because the error
vectors in y = v + e0 and e0 = 0 + e0 are equal. That ωy (x) = ωe0 (x) follows
from the fact that both are polynomials of degree ≤ deg(σy (x)) − 1 that coincide
on deg(σy (x)) distinct points.
So
Sy (x)σy (x) ≡ ωy (x) = ωe0 (x) ≡ Se0 (x)σe0 (x) ≡ Se0 (x)σy (x) (mod G(x)),
that is
(Sy (x) − Se0 (x))σy (x) ≡ 0 (mod G(x)).
The polynomials G(x) and σy (x) are relatively prime, because a common factor
would also divide ωy (x) by the Key Equation (1.3) and this contradicts the fact that
the degree of σy (x) was minimal. Hence, it follows that Sv (x) = Sy (x) − Se0 (x) = 0,
i.e. v ∈ C. This concludes the proof that y is of the form as described in equation
(1.2). It also concludes the proof of the proposition in the non–binary case.
The proof that the output v of At is of the form of Equation (1.2), with v ∈ C,
is similar to the non–binary case. u
t
Chapter 2
Adaptive chosen ciphertext attacks

on the McEliece cryptosystem
Summary. Attacks are introduced in which a malicious sender or an adaptive

eavesdropper Eve has an oracle which allows her to find out whether a ciphertext
does, or does not, decrypt properly. From this information Eve can extract the
plaintext that was encrypted. In this chapter it is shown that the McEliece public–
key cryptosystem is susceptible to these kinds of attacks. This chapter is based on
joint work with E. Verheul and H.C.A. van Tilborg [VDT02].
2.1 Introduction
In the last decade, several forms of attacks have been published where some of
the inputs of an encryption system with a secret fixed key are adaptively chosen.
By letting each new input (either plaintext or ciphertext) depend on the previous
outputs and by looking at certain aspects of the resulting output at each step,
additional secret information of the cryptosystem (for example the fixed key) may
be determined. Among the studied aspects of the output are:
• the differences in the output when the differences in the plain inputs are known,
see [BS93], [Mat93];
• some statistical or number–theoretic aspects of the output of the cryptosystem
when errors are inflicted to the cryptosystem itself (e.g. by radiation), see for
instance [BS97], [BDL97];
• so-called side-channel attacks, where the generation of the output is studied
instead of the output itself. For instance, one can study the execution time
when the precise complexity of the underlying cryptographic process is known
[Koc96], or the power consumption of the cryptographic algorithm [KJJ99].
In this chapter, we will look at a different setting. Here the attacker Eve has
access (for instance by interception) to one or more encrypted messages (called
9
10 Adaptive chosen ciphertext attacks on the McEliece cryptosystem
ciphertexts) sent by Alice to a receiver Bob. Eve’s aim is to recover the plaintext(s)
of those messages.
Also suppose that Eve has access to an oracle that can tell her whether a ci-
phertext deciphers correctly or not. Oracles similar to this one were studied by
Goldwasser, Micali and Tong in [GMT82]. Note that this oracle is weaker then
the one that is usually supposed to be at Eve’s disposal: Eve only gains knowledge
whether or not the ciphertext is valid, but she is not given the decrypted ciphertext.
In practice, such an oracle might be easy to obtain: Eve may have access to
Bob’s decryption device or Eve might be an active eavesdropper. Another realistic
possibility is that Bob’s decryption device is in fact automated, and will send an
automatic reply if the decryption somehow went wrong, asking for a retransmission.
This reply can then be intercepted and used by Eve.
This setting was used in [Ble98] to attack protocols based on the RSA encryp-
tion standard PKCS #1. In this chapter, an efficient attack against the McEliece
cryptosystem will be presented. The general idea of this attack is based on the
following components:
(i). Eve alters the ciphertext slightly in such a way that there is a reasonable
probability that the message still deciphers correctly and submits the altered
message to her oracle.
(ii). Knowledge on whether the altered ciphertext deciphers correctly or not re-
veals new information and opens interesting new possibilities for adapting the
ciphertext.
Eve will continue to alter messages in this way, until she has retrieved enough
secret information. It is very likely that Eve will have to send a considerable number
of altered messages.
The aim of this attack is to recover the plaintext of a given ciphertext.
In this chapter, attacks on the McEliece [McE78] public–key cryptosystem will
be discussed. It is thus assumed that Eve has a validly encrypted McEliece message
for Bob which she can alter and for which she is able to find out (e.g. by using her
oracle) if the altered message remains a validly encrypted McEliece message.
The outline of this chapter is as follows: first the McEliece public–key cryptosys-
tem will be described in Section 2.2. Section 2.3 is the main part of this chapter;
there an effective message-recovery attack on the McEliece public–key cryptosystem
will be described based on the maximal error correcting property of the two widely
used decoding algorithms (See Property 1.2.2). In Section 2.4 some countermeasures
against the described attack are considered.
Related Work
The attack described here differs from the one in [Ber97] where it is assumed
that the (original) sender, instead of an eavesdropper, sends the same message more
than once using different random error vectors. Also, an independent description of
an algorithm, similar to ours, has appeared in [HGS99]. However, their algorithm
2.2 The McEliece Public–Key Cryptosystem 11
is significantly less efficient. Also, their conclusion that the McEliece cryptosystem
should not be used because of this attack is unsupported - in Section (2.4) effective
countermeasures will be discussed.
2.2 The McEliece Public–Key Cryptosystem

In 1978, McEliece [McE78] proposed a public–key cryptosystem based on the
general difficulty of decoding. Consider a generator matrix G, generating a q–ary
code C with parameters [n, k, d], which is constructed by a user Bob. Let 0 ≤ t ≤
e = b(d − 1)/2c and let At be an effective decoding algorithm for C that can correct
at most t errors.
Now, to use this in a cryptographic setting, Bob generates a random, invertible,
q–ary, k × k matrix S and a random permutation matrix P of size n × n. The public
key of Bob is G0 = SGP together with the value of t. The matrices, S, G, P are kept
secret. The idea is that G0 , although it generates a codespace C 0 which is equivalent
to C, behaves like a “random” generator matrix for which the decoding problem is
hard.
Now suppose that another user, say Alice, wants to encrypt a message m ∈ Fkq
for Bob. To this end she generates a random error vector e of weight w(e) ≤ t and
forms:
r = mG0 + e (= mSGP + e). (2.1)
Note that in some variants the weight of the error vector e is always exactly equal
to t. On delivery, Bob calculates
rP −1 = (mS)G + eP −1 .
As eP −1 has the same weight as e, Bob can determine mS (and eP −1 ) from

−1
rP by means of his effective decoding algorithm At . Since S is a invertible matrix,
Bob can easily determine m, for instance by the method of Gaussian elimination.
More in particular, in the original scheme McEliece proposed to use binary (i.e.
q = 2), irreducible Goppa codes, with n = 1024, k ≈ 524 and t = 50. There exist
many (different) codes of these parameters, they are easy to generate (randomly)
and efficient decoding algorithms for them are easy to find. McEliece’s construction
can be extended to larger classes of codes (for instance non–binary Goppa codes).
No details will be given here as that is not necessary for the attack; it suffices to
mention the following bounds on the security–related parameters of the system.
Assumption 2.2.1 (The security of McEliece cryptosystem) The following ob-

servations can be made on the parameters of a McEliece public–key cryptosystem:
Sec–1. k ≈ n/2 ≥ 512: this makes “syndrome decoding” as well as an exhaustive

search for finding the nearest codeword to the received word infeasible;
Sec–2. 50 ≤ t ≤ 100: this makes all kinds of techniques that are based on guess-
ing/finding k (almost) error free coordinates less time consuming than the
methods in Sec–1, but still infeasible (see [BKT99; Dum96; McE78]).
The maximal error property (Property 1.2.2) states that the decoding algorithm
At , on input r, never returns an element c ∈ C at distance more than t from r. It is
important to realize that if too many transmission errors have occurred, the received
vector r may be at distance ≤ t from another codeword than the transmitted one.
In this case At will not return an error message. The probability that this occurs,
will be of importance in the analysis of the attack and will be discussed in Section
2.3. Recall (see Proposition 1.2.3) that the two relevant decoding algorithms for
Goppa codes have the maximal error property.
2.3 An adaptive chosen ciphertext attack
Now the attack on the McEliece cryptosystem will be described.
Algorithm 2.3.1 [Adaptive chosen ciphertext attack on McEliece]

Assume that the decoding algorithm At used in a McEliece cryptosystem has
the maximal error property. Let r be the ciphertext sent by Alice and intercepted
by Eve (it is of the form rA = mG0 + eA ). Then Eve does the following:
Step 1. Increase the number of errors made by Alice to exactly t.

In order to increase the number of errors to the maximum, Eve repeatedly
changes a random coordinate arbitrarily (though each coordinate is selected
at most once) and sends the resulting codeword to Bob until an error message
is returned, i.e. the message is not accepted as a valid McEliece ciphertext.
Once this occurs, Eve knows that this message contains exactly one error too
much, and thus that the previous message she sent to Bob has the maximum
number of errors. She now goes on to Step 2 with this message r0 .
Step 2. Determine enough error–free coordinates.
Once Eve knows she has a message r0 with exactly t errors, she can start
probing a random coordinate (different from all preceding choices, including
those made in Step 1) by changing this arbitrarily in r0 , and sending the
mutated message to Bob. If an error message is returned, this coordinate
was error–free. Once enough error–free coordinates are determined, Eve can
determine the plaintext in Step 3.
Step 3. Determine the plaintext.
Once Eve knows enough error–free coordinates, she can solve the matrix equa-
tion r0 = mG0 for the plaintext m by using Gaussian elimination on the
columns corresponding with the (known) error–free coordinates.
Before analyzing this algorithm, we introduce the following notion.

2.3 An adaptive chosen ciphertext attack 13
Definition 2.3.2 The weight distribution {Aw } of an [n, k, d] code C will be called
approximately binomial if (in the context of the problem here) the weight distribution
may be approximated as follows:
n
w
w (q − 1)
Aw ≈ , d ≤ w ≤ n. (2.2)
q n−k
Note that in this case,
n n n

X X (q − 1)w (1 + (q − 1))n
Aw ≈ w
= = q k = |C|,
w=0 w=0
q n−k q n−k
as it should be. Certainly the weight distribution of Fnq itself is binomial (in this
case the approximation in (2.2) is actually an equality). We are not familiar with
any result on how well the weight distribution of Goppa codes can be approximated
by the binomial distribution, but based on [KFL85; KL95] and [MS77, Section 9.10]
it seems very reasonable to make that assumption here.
For simplicity it will also be assumed that the minimum distance of the used
code is odd, i.e. d = 2t + 1.
Theorem 2.3.3 With the notation of Section 2.2, let the McEliece–like cryptosys-
tem be based on a q–ary code C with an approximately binomial weight distribution,
for instance a Goppa code. Also assume it uses a decoding algorithm that has the
maximal error property. Then Algorithm 2.3.1 is an adaptive chosen ciphertext
attack on C returning the plaintext m.
Before proving Theorem 2.3.3 two lemmas are needed. First recall that the
binary entropy function h(x) is defined on the interval [0, 1] by h(0) = h(1) = 0 and
h(x) = −x log2 (x) − (1 − x) log2 (1 − x) if 0 < x < 1.
Lemma 2.3.4 In the notation of Section 2.2, let e ∈ Fnq be an ‘error–vector’ of
weight t + 1. Then the following holds:
i) There is at most one vector f ∈ Fnq of weight ≤ t such that e + f ∈ C. Also, if
such an f exists, then the weight of f is exactly equal to t, the supports (the
sets of non–zero coordinates) of e and f are disjoint and d = 2t + 1.
ii) If e is chosen uniformly random, then the probability P that a vector f of weight
at most t exists such that e + f ∈ C is given by
A2t+1 2t+1

t+1
P = n
t+1
. (2.3)
t+1 (q − 1)
iii) If the weight distribution of C is approximately binomial, then

n−(t+1) t
2(n−(t+1))h( n−(t+1) ) (q − 1)t

t (q − 1)t
P ≈ ≤ ,
q n−k q n−k
where h is the binary entropy function.
iv) Assume that the weight distribution of the Goppa codes is indeed approximately
binomial. If a binary Goppa code is used in a McEliece cryptosystem, the above
probability P is negligible. To be more precise, when the parameters originally
proposed by McEliece in [McE78] are used, we have P ≤ 2−215 . When the
improved parameters as mentioned in Assumptions 2.2.1 are used, we have
that P ≤ 2−54 .
Proof:
i) Suppose that two distinct candidates for f – as mentioned in the first part of the
lemma – exist, say f and f 0 . Then
d(e + f , e + f 0 ) = d(f , f 0 ) = w(f − f 0 ) ≤ w(f ) + w(f 0 ) ≤ 2t < d.
As e + f and e + f 0 are two distinct members of C at distance less than d, we

arrive at a contradiction. A similar argument shows that the weight of f must
be equal to t and that d = 2t + 1.
ii) Let
B = {(e, f ) ∈ Fnq × Fnq | e + f ∈ C, w(e) = t + 1, w(f ) = t}.
Let c be a codeword in C of weight 2t + 1. Then each (t + 1)–subset of the

support of c gives rise to a unique pair (e, f ) ∈ B (change the remaining t
non–zero coordinates of c into a zero, resp. the t + 1 coordinates themselves).
(e, f ) ∈ B can be obtained this way. Hence it follows
Conversely, each element
that |B| = A2t+1 2t+1
t+1 .
n

The total number of ‘error–vectors’ of weight t + 1 in Fnq is t+1 (q − 1)t+1 .
The probability P is the quotient of |B| and this number.
iii) By assumption the relation

n

2t+1 (q − 1)d
A2t+1 ≈
q n−k
holds. It follows from ii) that

n 2t+1 2t+1 n−(t+1)

2t+1 (q − 1) t+1 t (q − 1)t
P ≈ n
= n−k
.
q n−k t+1 (q − 1)t+1 q
To arrive at the inequality in iii), note that the binomial theorem implies the
inequality
n
X n n
nn = (m + (n − m))n = mi (n − m)n−i ≥ mm (n − m)n−m
i=0
i m
2.3 An adaptive chosen ciphertext attack 15
for each 0 ≤ m ≤ n. This can be rewritten as
nn 2n log2 n

n
≤ = =
m mm (n − m)n−m 2m log2 m 2(n−m) log2 (n−m)
2−m log2 (m/n)−(n−m) log2 ((n−m)/n) = 2nh(m/n) .
Note that since

n
n n
X n i n−i n
n = (m + (n − m)) = m (n − m) ≤ (n + 1) mm (n − m)n−m ,
i=0
i m
it also follows that

n nh(m/n) n
≤2 ≤ (n + 1) .
m m
Note that this inequality is often used in the literature, in the form

nh(m/n) n 1
2 ≥ ≥ 2nh(m/n) = 2n(h(m/n)−log2 (n+1)/n)
m n+1
n

to prove that for 0 ≤ α ≤ 1 and as n tends to infinity, αn = 2nh(α) .
iv) With the assumption that the weight distributions of the Goppa codes are
indeed approximately binomial, the probability P mentioned in ii) can be
approximated using iii). If the parameters proposed by McEliece are used, i.e.
n = 1024, k = 524, t = 50, the probability P can be approximated by
2975∗h(50/975) 2285
P ≤ 500
≈ 500 = 2−215 ,
2 2
which is negligible. Similarly, P ≤ 2−54 if the parameters are as in Assumption
2.2.1. So the same holds for general McEliece cryptosystems, provided of
course the weight distribution of the used code is approximately binomial.
u
t
The following observation may be of interest to the reader. It is well known that
for a perfect t–error correcting code 2t+1 n
t+1
t A2t+1 = t+1 (q − 1) (see for instance
[Til93a, Problem 3.4.9]). Substitution of this relation into (2.3) gives P = 1, as
it should be for a perfect code: each word at distance t + 1 from one codeword
lies at distance t from exactly one other codeword. Thus a Sloppy Alice attack
on McEliece–like cryptosystem which uses a perfect code will not work, since each
vector can be decoded and thus no error messages will be generated.
Lemma 2.3.5 The probability that a random k × (k + logq k) q–ary matrix has rank
k is at least 1 − k1 .
Proof: Let P (k, m), m ≥ k, denote the probability that a random k × m binary
matrix A has rank k. Looking at the rows of A we observe that the first row of A
should be non–zero, the second row should be independent of the first, etc. This
argument leads to
Qk−1 m
i=0(q m − q i ) Y 1
P (k, m) = Qk−1 m = (1 − i )
i=0 q
q
i=m−k+1
(∗) m
X 1 1 − q1k 1
≥ 1− = 1 − ≥ 1 − m−k ,
qi (q − 1)q m−k q
i=m−k+1
where (∗) follows quite easily with an induction argument. Now substituting m =
k + logq k in the above relation gives
1
P (k, k + logq k) ≥ 1 − .
k
u
t
Now the main theorem can be proven:
Proof of Theorem 2.3.3: Consider any r = c + e where c ∈ C and w(e) = s ≤ t.

If the ith coordinate of r is changed, which can be described by adding a vector
u of weight 1 and with support {i} to r, then there are three possibilities for the
resulting r0 = r + u = c + e0 (only two if q = 2):
(i). w(e0 ) = s − 1 if and only if ei 6= 0 and ui = −ei ,
(ii). w(e0 ) = s if and only if ei 6= 0 and ui 6= −ei
(This is impossible if q = 2, because both are also non–zero in this case),
(iii). w(e0 ) = s + 1 if and only if ei = 0.
Consider Step 1 of Algorithm 2.3.1. For the range 0 ≤ i ≤ 2t+1, let e(i) = r(i) −c,
that is, r(i) = c + e(i) . Of course each e(i) is unknown to Eve and e(0) = eA . As
w(e(0) ) = w(eA ) ≤ t it follows that there exists a first 0 < i ≤ 2t + 1 in Step 1,
such that w(e(i) ) = t and w(e(i+1) ) = t + 1. So, for 0 ≤ j ≤ i the execution of the
decoding algorithm At applied by Bob to r(j) does not result in an error–message.
Note that i can only reach the value 2t + 1 in the (extremely unlikely) case that
the 2t + 1 errors introduced by Eve in this step of the attack algorithm include all
the errors that Alice originally has added to c. In this case, we can immediately
proceed to Step 3 of the algorithm since all other coordinates will be error–free, and
contain enough independent columns of the generator matrix G0 .
Next, it is claimed that the At applied to r(i+1) = c+e(i+1) with e(i+1) of weight
t + 1, will result in an error–message (and we go to Step 2). Indeed, if At applied to
r(i+1) does not issue an error–message then r(i+1) lies at distance at most t from C
by the maximal error property. This means that there exist a codeword c0 in C and
2.4 Countermeasures 17
a vector e0 in Fnq of weight at most t such that ri+1 = c0 + e0 . Hence, the situation
of Lemma 2.3.4 applies, from which it follows that this situation has a negligible
probability of occurring.
In Step 2, write r0 = c + e0 , with w(e0 ) = t. Following the same reasoning as
above, when the f –th coordinate in r is changed, the obtained vector r̂ will not
be accepted by At (i.e. without error–messages) if and only if (with a negligible
probability of failure) the f –th coordinate of e0 is zero. u
t
Theorem 2.3.6 Let the number of times the loop in Step 1 is executed be S1 . With
large probability the loop in Step 2 will be executed at most k + logq (k) + X + 1 times,
where X = min(t, 2t + 1 − S1 ).
Corollary 2.3.7 With large probability Algorithm 2.3.1 is an adaptive chosen ci-
phertext attack which uses at most k + logq (k) + 2t + 2 oracle queries.
Note that if a binary code is used, there is only one possibility for an error–
coordinate. In that case Algorithm 2.3.1 can be improved to an attack of at most
k + 2t + 1 oracle queries. Also note that if in Step 2 of Algorithm 2.3.1 t rejections
are encountered, all errors introduced by Alice have been found and all remaining
coordinates are error–free. In this case deciphering can be done much faster. Of
course, the probability that this occurs is negligible.
Proof of Theorem 2.3.6: The number of loops in Step 2 of the algorithm follows
directly from Lemma 2.3.5. Since in this step only coordinates different from those
selected in Step 1 are taken, an extra term +X must be added that reflects the
(marginal) possibility that X times a change made in this step canceled out an
error introduced by Alice. Thus the number of oracle queries needed in Step 2 of
the algorithm is equal to k + logq (k) + S1 + X.
However, if a change in Step 2 canceled out an error introduced by Alice, this
error could not have been canceled in Step 1. Also, the number of oracle queries in
Step 1 is at most 2t + 1. Thus the sharper bound S1 + X ≤ 2t + 1 holds. Because
S1 +X ≤ 2t+1, with large probability the algorithm uses at most k +logq (k)+2t+1
oracle queries. u
t
2.4 Countermeasures
Countermeasures to the adaptive chosen ciphertext attack on the McEliece cryp-

tosystem should at least aim to achieve that there is no correlation between deci-
phering problems and the number of errors applied to the plaintext.
First, in the case that Bob is Eve’s oracle, Bob could come up with the idea of
checking for repeated messages. This would detect an attack as described above,
but nothing prevents the attacker Eve from adding a random codeword from C to
her probe each time she queries the oracle. This preserves the error–vector e, and
will allow Eve to conduct her attack as usual with little additional effort.
As a second idea one might consider to fix the weight of the error vector to
exactly t, (or any t0 ≤ t). (cf. Equation (2.1)) and to return an error–message when
in the deciphering process an error vector is encountered of weight unequal to t (or
the chosen t0 ), that is, irrespective of whether successful decoding is still possible.
However, in this setting effective attacks are still possible. First of all, suppose
that the used code is non–binary. If one ‘probes’ a coordinate in Step 2, say the
i–th coordinate, twice but with different values, then Bob will always return an
error–message if that coordinate is error–free (since there are t + 1 errors in both
probes). However, if there’s an error on that coordinate, at most one probe will
return no error message (since Eve only alters the value of ei and not the weight of
the error–vector).
So we have the following situation:
• if both probes give an error–message, then ei = 0,
• if only one probe gives an error–message, then ei 6= 0 and ei is in fact deter-

mined,
• if none of the probes gives an error–message, then ei 6= 0.
It easily follows that the plaintext can be found with approximately k + t probes,
i.e. in approximately 2(k + t) oracle queries.
If the used code is binary, then one starts by changing any coordinate, say the
i–th, of r0 . In the setting here, this will always lead to an error–message from the
oracle. Now we distinguish two possibilities.
With probability (n − t)/n one has that ei = 0. If one changes an additional
coordinate in all possible ways, then n − t − 1 times another error will have been
introduced, resulting in an error–message from the oracle. Further, t times an error
(introduced originally by the original sender) will be eliminated and so in this case
one is back at t errors, leading to a correct decryption. In this way, all errors
introduced by Alice can be found.
If ei = 1 (with probability t/n), then additionally introduced single errors will
n − t times lead to correct decryptions (and coordinates with ei = 0) and t − 1 times
to an error message.
In the case that Bob is in fact serving as Eve’s oracle, a better countermeasure
to the attack technique may be to introduce further redundancy in the system to
enable Bob to check if an active eavesdropper is altering a proper ciphertext.
For instance, let Alice choose her plaintext m from Fk−128 q instead of Fkq . As
before, she chooses a random error vector of weight ≤ t. Bob has published as part
of his public key a cryptographically secure hash–function h that maps bit strings
of arbitrary length to elements in F128 q (this hash function can also be a system
parameter). To encrypt m Eve computes (cf. Equality (2.1)):
r = (m||h(m||e))G0 + e (= (m||h(m||e))SGP + e), (2.4)

0
where || stands for concatenation. When Bob receives a vector r , he will attempt
2.5 Conclusion 19
to decode it. If this works, he will find an error vector e0 and an element m0 ∈ Fkq
satisfying
r0 = m0 G0 + e0 .
Finally, he checks the hash value of the message and the error vector. If this
verification fails, an error–message is issued. This error–message will not give any
information to Eve about the original choice of e by Alice, since any error results
in rejection. It follows that the attack as described in Section 2.3 fails.
Note that the choice of 128 bits in the above example is arbitrary: this is a
security parameter of the system which indicates how many message bits are used
to increase security. We refer to [FO99] for a general description of this construction.
Also observe that as a side effect of this variation the McEliece cryptosystem loses
its inherent error–correcting capabilities. This seems to be inevitable.
2.5 Conclusion
In this chapter an adaptive chosen ciphertext attack was introduced, which is
based on the assumption that (ordinary) users may see no problem in revealing
whether or not an encrypted message deciphers correctly. Such a Sloppy Alice
attack on the McEliece public–key cryptosystem was analyzed in detail.
The general conclusion is that such error–messages can be used to efficiently
decrypt any message encrypted with the McEliece cryptosystem. Therefore, at the
very least, error–messages should be as non–descriptive as possible and users should
be alerted when many encrypted messages do not decrypt properly. Also, a variant
of the McEliece cryptosystem which is immune to attacks was proposed.
Chapter 3
Digital signature schemes based on

error–correcting codes
Summary. In this chapter the security of digital signature schemes based on

error–correcting codes is discussed. Several attacks against the Xinmei scheme are
surveyed and some reasons for the failure of the Xinmei scheme are given. Another
weakness is found in the Alabbadi–Wicker scheme. This weakness leads to a uni-
versal forgery attack against it. Further analysis shows that this new weakness also
applies to the Xinmei scheme. This chapter is based on joint work with S.B. Xu
and H.C.A. van Tilborg [XD99; XDT03].
3.1 Introduction
The concept of digital signatures was proposed by Diffie and Hellman when
they introduced public–key cryptography in their pioneering paper [DH82]. When
Alice wants to sign a message m and send the signature to Bob, she sends the pair
(m, s) where s is the signature s = Sign(m). Bob can then verify the signature by
applying Alice’s public verification algorithm Ver to s (thus the relation Ver(s) =
Ver(Sign(m)) = m must hold). Sometimes, the message m is even omitted. In
that case, the verification algorithm will return the message m. Such a scheme is
called a message recovery scheme. See for instance [MOV97, Chapter 11] for more
information on this subject.
Digital signatures play an important role in electronic commerce because they
can replace a written signature. Several digital signature schemes are based on
the integer factorization problem (e.g. RSA [RSA78]) and the discrete logarithm
problem (e.g. ElGamal [ElG85]). People are now trying to design new digital
signature schemes based on other mathematically hard problems. The problem of
decoding general linear codes is such a problem, which has been proven to be NP–
complete by Berlekamp, McEliece and Van Tilborg [BMT78]. McEliece [McE78] first
proposed a public–key cryptosystem based on linear error–correcting codes, which
derives its security from the above general decoding problem. No efficient attack on
21
22 Digital signature schemes based on error–correcting codes
McEliece’s cryptosystem has been found until now, though several computationally
intensive attacks have been discussed in the literature [Cha95; Ber97; CS98] and
attacks on implementations of the McEliece cryptosystem have been published (see
e.g. [HGS99; VDT02] and also Chapter 2 of this thesis). Since 1978, several other
cryptosystems based on error–correcting codes have been proposed, such as the Rao–
Nam private–key cryptosystem [RN89], the Xinmei signature scheme [Wan90] and
the Stern identification scheme [Ste93]. These schemes are either used to protect the
secrecy or to provide the authenticity of the message according to different needs.
In this chapter the security of digital signature schemes based on error–correcting
codes is discussed.
Some public–key cryptosystems can directly be used as digital signature schemes,
for instance the RSA cryptosystem [RSA78]. However, McEliece’s public–key cryp-
tosystem cannot be used directly as a digital signature scheme because its encryption
function maps binary k–tuples to binary n–tuples. Since this mapping is not sur-
jective [MOV97, Section 8.5], it can not be inverted. Thus almost no messages can
be signed, since no k-tuple exists that maps onto this particular message.
In 1990, Xinmei Wang proposed the first digital signature scheme based on error–
correcting codes [Wan90], referred to as the Xinmei scheme. In the Xinmei scheme,
the signature is generated in a manner similar to the way plaintext is encrypted in
the Rao–Nam private–key cryptosystem [RN89]. The Xinmei scheme was claimed to
have its security rely on the large number of generator matrices of a particular error–
correcting code and the difficulty of retrieving a particular one from its scrambled
public equivalents. In 1992, several methods were proposed to attack the Xinmei
scheme. Harn and Wang [HW92] first proposed a homomorphism attack on the
Xinmei scheme without factoring large matrices, and presented an improved scheme
(here called the Harn–Wang scheme) in which a nonlinear function is introduced
to defeat the homomorphism attack. Then, Alabbadi and Wicker [AW92b] showed
that the Xinmei scheme is vulnerable to a chosen plaintext attack with complexity
O(n3 ). They [AW92a] also showed that the Harn–Wang scheme can be broken
completely by a known plaintext attack with complexity O(k 3 ). Later, Van Tilburg
[Til92] showed that one can directly obtain the signature key from the public keys
in both the Xinmei scheme and the Harn–Wang scheme. In 1993, Alabbadi and
Wicker [AW93] proposed a new digital signature scheme based on error–correcting
codes. In the same year, Van Tilburg [Til93b] showed that this new scheme is
not secure if one is able to verify n signatures (with linearly independent error
vectors). In 1994, Alabbadi and Wicker [AW94] proposed a universal forgery attack
on the Xinmei scheme and their own scheme. Later that year, Alabbadi and Wicker
[AW95] presented another digital signature scheme based on error–correcting codes,
which will here be referred to as the Alabbadi–Wicker scheme. They claimed that
the proposed scheme is resistant to the attacks that proved successful when used
against the aforementioned digital signature schemes.
Courtois, Finiasz and Sendrier recently proposed [CFS01] a digital signature
scheme based directly on the McEliece cryptosystem. They argued that the problem
of the non–surjective encryption mapping is not insurmountable: the probability
3.2 Security analysis of the Xinmei scheme 23
that a random McEliece ciphertext is valid, i.e. the probability that it can be
decrypted is about t!1 . Thus, by successively trying about t! different ciphertext
candidates, formatted as the concatenation of a hash of the message m and a counter
0 ≤ i ≤ t!, a valid signature can be obtained.
The subsequent sections are organized as follows: in the second section, the Xin-
mei scheme will be introduced and studied. In the third section the Alabbadi–Wicker
scheme will be described. Then a universal forgery attack against the Alabbadi–
Wicker scheme will be presented. Finally, some comments about the security of
digital signature schemes based on error–correcting codes are made.
3.2 Security analysis of the Xinmei scheme

3.2.1 Description of the Xinmei scheme
The Xinmei scheme works as follows:
Setup phase: Alice takes a (k ×n) generator matrix G of a binary Goppa code
with an error–correcting capability of t errors of which t0 errors can be corrected
efficiently. She also chooses a right inverse matrix G−R of G, so G−R satisfies
GG−R = Ik , where Ik is the k × k identity matrix. Furthermore, she chooses a n × n
full rank random matrix R and a k × k full rank matrix S, called the scrambling
matrix.
Alice then publishes her public keys t, t0 (< t), H, J, W and T , which are given
by:
J = R−1 G−R S −1 ,
W = G−R S −1 ,
T = R−1 H T ,
where H is the parity check matrix of the Goppa code in the usual form (1.1), in
particular GH T = 0. Alice’s private keys are R and the matrix product SG.
Signature phase: The signature s of a k–bit message m is obtained by
computing
s = (e + mSG)R,
where e is a random n–bit error vector of Hamming weight w(e) ≤ t0 , chosen by

Alice. After the signature s is calculated, Alice sends the pair (m, s) to Bob.
Verification phase: The authenticity of a message–signature pair (m, s) can
be checked in the following way:
(i). Calculate the syndrome
sT = [(e + mSG)R]R−1 H T = eH T + mSGH T = eH T .
(ii). Let e0 be the result of the Berlekamp–Massey algorithm applied to the above
syndrome sT . It is possible to calculate this since the parity check matrix H
is in the usual form (1.1). If t0 < w(e0 ) < t, 1

Bob rejects the signature. Note
that e = e0 , since w(e) ≤ t0 .
(iii). Verify whether the relation m = sJ − e0 W holds as it should do, since
sJ = (e + mSG) R R−1 G−R S −1 = eG−R S −1 + m = eW + m,

and e0 = e. If this is the case, the signature is valid. Otherwise reject the
signature.
Note that if in the setup phase a permutation matrix was taken for R, the Xinmei
scheme reduces to the Rao–Nam private–key cryptosystem. It has been shown in
[RN89] that the matrix SGR can be determined through majority voting if the
Hamming weight of the n–bit error vector e is not in the neighborhood of n/2.
3.2.2 Some weaknesses in the Xinmei scheme

As mentioned in the introduction, the Xinmei scheme is vulnerable to several
types of attacks. In the following these attacks will be surveyed and an analysis of
why the Xinmei scheme is susceptible to them will be presented.
• Homomorphism attack [HW92]. Since the error vectors e are revealed during
the verification, Eve can choose two message–signature pairs satisfying w(e1 +
e2 ) ≤ t0 . Then s1 + s2 will be a valid signature for the message m1 + m2 .
Obviously, the linearity of the signature in the Xinmei scheme results in this
homomorphism attack. To thwart this attack, Harn and Wang suggested
modifying the Xinmei scheme with a hash function h by setting s = (e +
h(m)SG)R.
• Chosen–plaintext attacks [AW92b]. If Eve is able to get n + 1 different pairs of

signatures and error patterns for the same message m in which n signatures
are linearly independent, Eve can obtain the secret matrix R using the relation
D = ER where D and E are the n × n matrices with as ith row si respectively
ei (1 ≤ i ≤ n).
Once R is known, Eve can obtain the other secret key SG through the following
chosen–plaintext attack: suppose Eve has obtained k message–signature pairs
for a set of linearly independent messages. Using the error patterns from the
verification procedure, Eve can calculate SG from the equation E 0 = M SG
where E 0 and M are the k × n matrices with as ith row si R−1 − ei respectively
mi .
The linearity of the signature enables Eve to successfully recover the secret keys
R and SG in the above chosen–plaintext attacks. The knowledge of the error
patterns also plays an important role in this attack. In the Xinmei scheme the
random error vector is used to improve the security of scheme. Unfortunately,
1 The original equations are 2t0 − t > w(e0 ) > t. Obviously, they are wrong because t > t0 .
3.2 Security analysis of the Xinmei scheme 25
the leakage of the error vector results in the failure of the Xinmei scheme. To
defeat the above attack, Alabbadi and Wicker suggested to introduce a hash
function h(x, y) into the signature scheme [AW93]. In their scheme h(x, y) is
used to hash the k–bit message m and the n–bit error vector e to replace the
k–bit message in the signature generation of the Xinmei scheme.
In addition, Alabbadi and Wicker proved that the Harn–Wang scheme is sus-
ceptible to a known–plaintext attack [AW92a].
• Directly recovering the secret keys from the public keys. In the above attacks,
Eve can calculate the signers secret keys from some triplets of messages, sig-
natures and error patterns. Van Tilburg [Til92] also showed that the secret
keys in the Xinmei scheme can be recovered directly from the public keys.
Since G and H T are orthogonal matrices, one can find a so–called analogous
generator matrix G̃ = QG where Q is an unknown nonsingular k × k matrix.
Following this, an analogous scrambling matrix S̃ can be obtained by inverting
G̃W = QGG−R S −1 = QS −1 = (S̃)−1 . The original secret key SG then follows
from S̃ G̃ = SQ−1 QG = SG. Finally R can be recovered from the equation
[J S̃ G̃|T ] = R−1 [W S̃ G̃|H T ]. Van Tilburg proved that [W S̃ G̃|H T ] has rank n.
Thus the Xinmei scheme can be totally broken. The same attack also applies
to the Harn–Wang scheme.
Alabbadi and Wicker also tried to recover G from H and they estimated that
the search is infeasible because it has complexity O(k!) [AW92b].
Without question, it is the redundancy in the public keys that results in the
above attack. However, in order for Bob to check the validity of a signature,
Alice has to publish some necessary public keys. Firstly Bob needs to have
the ability to decode the signature. Thus the public key has to include some
information about the parity check matrix. In the Xinmei scheme and also in
other schemes, Bob is supposed to have the ability to recover the error pattern
from the signature by means of the Berlekamp–Massey algorithm. However,
the Berlekamp–Massey algorithm requires the parity check matrix to be in
the usual form (1.1) [MS77]. Thus the parity check matrix has to be public,
if either Euclid’s or the Berlekamp–Massey algorithm is used for decoding.
Furthermore, Bob needs to recover the message, whether in hashed form or
not, from the signature using some public keys. These public keys and the
verification procedure undoubtedly leak information about the secret keys.
• Potential threats from analogous matrices. Is it possible for Bob to completely

defeat forgery attacks by recovering the message and checking if it is equal to
the received message in the Xinmei scheme and other schemes [AW93; AW95]?
Some potential threats from analogous matrices of secret keys are explored in
this chapter.
Firstly, the generator matrix G is the most important secret key in the Xin-
mei scheme and other schemes [AW93; AW95]. Even though Eve knows the
parameters (length n, dimension k and minimum distance d) of the code used

in these schemes, it is still difficult for her to find G. For each [n, k] binary
linear code, there are (2k − 1)(2k − 2) · · · (2k − 2k−1 ) different generator matri-
ces. As a secret key the generator matrix G is protected by two nonsingular
random matrices S and R against direct calculation by the attacker (by using
the public keys and the verification procedure).
Different generator matrices define different mappings from messages to sig-

natures. But it is difficult to design a verification procedure which can check
whether the signature satisfies the real mapping. This is because the real
mapping is not known by either Bob or Eve (otherwise the scheme would
be broken). However, Eve can obtain an analogous generator matrix G̃ from
G̃H T = 0k×(n−k) (where 0 is the all-zero matrix) because she knows the parity
check matrix H. This analogous matrix G̃ can be found in polynomial time.
Then Eve can use G̃ to forge a signature. It is possible for the forged signature
to pass the verification procedure because all items related to G̃ in the sig-
nature usually can be canceled in the procedure of calculating the syndrome.
In addition, this can also happen to other secret keys. Thus it is possible for
Eve to forge a signature which can pass the other checks in the verification
procedure.
In Section 3.5 this method will be used to break the Alabbadi–Wicker scheme.
3.3 The Alabbadi–Wicker scheme

The three phases of the Alabbadi–Wicker scheme can be described as follows:
Setup phase: in the setup phase, each user chooses a t–error correcting binary
irreducible Goppa code C with length n = 2m and dimension k. The code is
described by an irreducible polynomial G(z) of degree t and coefficients in F2m .
Alice then selects a k × n binary generator matrix G and a (n − k) × n binary parity
check matrix H for the chosen code. She then chooses two k × n binary matrices
W and V such that
G = W + V, (3.1)
where the rank of W is k. This means that there exists an n × k binary right–inverse
matrix W −R such that
W W −R = Ik , (3.2)
where Ik is the identity matrix. The matrix W −R is chosen such that GW −R has
nonzero rank k 0 < k. Then she generates a nonsingular n × n binary matrix R. The
final step of initializing the signature scheme is the computation of the following
3.3 The Alabbadi–Wicker scheme 27
matrices:
H 0 = R−1 H T , (3.3)
W 0 = R−1 W −R , (3.4)
W 00 = W −R GW −R . (3.5)
Alice then publishes G(z), W −R , H 0 , W 0 , W 00 , t and t0 < t as public keys. The

private key consists of the matrices V , W , G, W −R G, and R.
In addition a hash function h : F2k × F2n → F2k is made available to all users of
the system.
Signature phase: suppose user Alice wants to sign a k–bit message m. She then
selects two binary vectors at random: a n–bit vector e of weight t0 , and a k–bit
vector r of arbitrary but nonzero weight. The signature (s, x) of the message m is
then computed as follows:
x = (rG + h(m, e)V ) R,

s = e + h(m, e)W + xW −R G R.

Finally, Alice transmits the triplet x, s, and m to Bob.
Verification phase: Bob gets a signature (x, s) along with the message m. The
signature validation is then performed as follows:
(i). The following expression is computed:
rG + h(m, e)V + e + h(m, e)W + xW −R G R

x+s =
= rG + h(m, e)G + e + xW −R G R.
(ii). The syndrome is calculated:
(x + s)H 0 = rG + h(m, e)G + e + xW −R G RR−1 H T

= eH T .
(iii). The Berlekamp–Massey algorithm is applied to the above syndrome to obtain

the error vector e. If w(e) 6= t0 , Bob rejects the signature.
(iv). The hash h(m, e) of the message and the error vector is recovered from x, e,
and s by computing
sW 0 + xW 00 + eW −R = sR−1 W −R + xW −R GW −R + eW −R
−R
−1 −R
= e + h(m, e)W + xW G R R W +
+xW −R GW −R + eW −R
= eW −R + h(m, e) + xW −R GW −R +
= h(m, e).
(v). Finally, Bob compares the result of the above computation to h(m, e), which
he can calculate himself. If they are equal, he accepts the signature as valid.
Apparently, the proposers of this scheme overlooked the fact that step (iii) of
this verification procedure will not work, since applying the Berlekamp–Massey algo-
rithm requires the parity check matrix to be in the usual form (1.1) [MS77, Section
12.9]. Obviously, if this step is to work, Alice has to select H to be in the usual
form, and should thus make H public.
3.4 Modifying the Alabbadi–Wicker scheme

Since the verification phase of the Alabbadi–Wicker scheme will not work unless
the parity check matrix H is in the usual form (1.1), and thus public, a revision of
the scheme is needed. This revision is made here by modifying the three phases as
follows:
Setup phase: Alice first calculates the public keys as in the original Alabaddi-
Wicker scheme, as described in the previous section. Suppose that the order of
coordinates in F2m is chosen to be canonical (it could also be chosen by each user
individually, but it would then have to be part of the public key as well). Further-
more, let HΓ be the parity check matrix of the chosen Goppa code in the usual form
(1.1). Since the chosen matrix H is also a parity check matrix, Alice can find a
non-singular matrix M such that
HΓ = M H.
Alice then publishes G(z), W −R , H 0 , W 0 , W 00 , t and t0 < t as public keys. The

private key consists of the matrices V , W , G, W −R G, R and M .
Signature phase: suppose Alice wants to sign a k–bit message m. She then selects
two binary vectors at random: a n–bit vector e of weight t0 and a k–bit vector r
of arbitrary but nonzero weight. The signature (s, x) of the message m is then
computed in the following steps:
(i). Alice finds a solution f to the equation f HΓT = eHΓT M T directly. This is pos-
sible, since a solution surely exists (every syndrome occurs among all vectors
of Fn2 since we are dealing with a linear code). However, the solution will
obviously not be unique since no requirement on the weight is given. Thus f
satisfies
f H T = eHΓT .
(ii). Alice computes

x = (e + f + rG + h(m, e)V ) R,
s = e + h(m, e)W + xW −R G R.
3.5 Cryptanalysis of the Alabbadi–Wicker scheme 29
Finally, Alice transmits the signature (x, s) and the message m to Bob.
Verification phase: Bob gets a signature (x, s) along with the message m. He
validates the signature in the following steps:
(i). The following expression is computed:
rG + h(m, e)V + f + h(m, e)W + xW −R G R

x+s =
= rG + h(m, e)G + f + xW −R G R.
(ii). The syndrome is calculated:
(x + s)H 0 = rG + h(m, e)G + f + xW −R G RR−1 H T

= f H T = eHΓT .
(iii). The Berlekamp–Massey algorithm is applied to the above syndrome. The

result of the algorithm will be the error vector e. If w(e) 6= t0 , Bob rejects the
signature.
(iv). The hash h(m, e) is recovered from the signature (x, s) and the error vector
e by computing
sW 0 + xW 00 + eW −R = sR−1 W −R + xW −R GW −R + eW −R
= eW −R + h(m, e) + xW −R GW −R +
= h(m, e).
(v). Finally, Bob calculates the value h(m, e) and compares it to the last result. If
they are equal, he accepts the signature as valid.
3.5 Cryptanalysis of the Alabbadi–Wicker scheme

Alabbadi and Wicker claimed that their scheme is resistant to the attacks that
proved successful against the Xinmei scheme and also to other attacks. First the
resistance of the Alabbadi–Wicker against the attacks described in Section 3.2 will
be investigated.
3.5.1 Resistance of the Alabbadi–Wicker scheme against attacks

The Alabbadi–Wicker scheme looks similar to the Xinmei scheme (with a hash
function) if the signatures x and s are added:
x + s = rG + h(m, e)G + e + xW −RG R

= e + [r + h(m, e) + xW −R ]G R
= (e + h0 (m, e)S 0 G) R.
Note that the modified scheme retains this property. Alabbadi and Wicker adopted
different methods to defeat the attacks which are successful against the Xinmei
scheme. First a hash function h is applied to both the message m and the er-
ror vector e to prevent the homomorphism attack in Section 3.2.2. Furthermore a
k–bit vector r of arbitrary (but nonzero) weight has been introduced to the signa-
ture x. Bob cannot solve r from the signature x, and only Alice knows it. Thus
the Alabbadi–Wicker scheme defeats both the chosen–plaintext and the known–
plaintext attack in Section 3.2.2. Lastly the generator matrix G has been split into
two matrices W and V and the public keys (namely W −R , W 0 and W 00 ) include only
partial information about G (of course, the null space of G is determined by both
H and the polynomial G(z)). So at least it is difficult to directly derive the secret
key G from the public keys. A total break appears to be infeasible, primarily be-
cause the public keys do not completely describe G (this is true because the matrix
W 00 = W −R GW −R is not of full rank). Eve thus seems to be forced to perform an
exhaustive search through all possible generator matrices for the code C.
However, the Alabbadi–Wicker scheme is not as secure as they claimed. They
state that their digital signature scheme derives its security from the complexity
of three problems: the decoding of general linear error–correcting block codes, the
factoring of large matrices, and the derivation of a matrix from its right inverse.
In the following sections a universal forgery attack against the Alabbadi–Wicker
scheme will be presented.
3.5.2 A universal forgery of the Alabbadi–Wicker scheme

In [AW95], Alabbadi and Wicker analyzed the possibility of a universal forgery,
i.e. being able to sign an arbitrary message given only the public keys. Even though
their attack did not succeed, it did motivate the following attack using analogous
matrices.
Recovering the parity check matrix H
Even if H is not in the usual form, it is still possible for Eve to recover H from the
public keys and the verification procedure. From the second and the third step in
the verification of a signature the following equation can be obtained:
(x + s)H 0 = eH T , (3.6)
where x, s and e and H 0 are known to Eve. Note that the matrix dimensions of H T
and H 0 are the same.
Suppose Eve is able to obtain signatures with n independent error vectors ei and
thus the corresponding (xi + si )H 0 (1 ≤ i ≤ n). Then she can solve the parity check
matrix H T from the n Equations (3.6) by setting H T = E −1 (X + S)H 0 where E,
X and S are the matrices with as ith row respectively ei , xi or si (1 ≤ i ≤ n). The
complexity of solving H T in this way is only O(n3 ).
Calculating an analogous matrix R̃

After Eve has successfully recovered the parity check matrix H, she can try to find
the nonsingular matrix R according to the following method. From (3.3) and (3.4)
the following expression follows:
[H 0 |W 0 ] = R−1 [H T |W −R ], (3.7)
where H 0 and H T are n × (n − k) matrices and W 0 and W −R are n × k matrices.

So [H 0 |W 0 ], [H T |W −R ] and R−1 are n × n matrices. Alabaddi and Wicker proved
that [H T |W −R ] is a singular matrix, so Eve cannot find R−1 from Equation (3.7).
Even so, she can obtain an analogous matrix R̃−1 which can also be used to forge a
signature.
Even though [H T |W −R ] is not a full rank matrix, Eve can obtain a nonsingular
row transformation matrix R̃−1 from (3.7), which satisfies the following equations:
H 0 = R̃−1 H T , (3.8)
W 0 = R̃−1 W −R . (3.9)
Of course, it would be best if the matrix R̃−1 is equal to R−1 . However, Eve has
no way of knowing this. The attack still goes through, even if the two matrices are
not equal. Eve may calculate the inverse matrix R̃ from R̃−1 in polynomial time.
The matrix R̃ will play an important role in the following universal forgery.
Universal Forgery for the Alabaddi-Wicker scheme

Eve will now calculate an analogous generator matrix G̃ which should satisfy
G̃H T = 0k×(n−k) . (3.10)
Note that G̃ is in general not equal to G, the generator matrix used by Alice (just
like with the above R̃), but again this does not matter.
Since W −R is a public key, Eve can calculate a left inverse W̃ of W −R , so
W̃ W −R = Ik . (3.11)
Then Eve calculates Ṽ = G̃ + W̃ . Again, in general V 6= Ṽ and W 6= W̃ .

Since W 00 and W −R are public keys, Eve can calculate a matrix Ỹ by simple
algebraic means which satisfies the following equation.
W 00 = W −R GW −R = Ỹ W −R . (3.12)
Now Eve is able to forge the signature of any message m. According to Alabbadi–
Wicker scheme, an n–bit error vector e of weight t0 is chosen at random. Since r is
only used to protect G from the attacks in Section 2, it is discarded (after all, she
is trying to forge a signature, not to obscure G).
To obtain a signature for the message m, Eve first calculates the vector x of the
signature pair (x, s) from the implicit equation

x = h(m, e)Ṽ + xỸ R̃. (3.13)
Then she can calculate s from

s = e + h(m, e)W̃ + xỸ R̃. (3.14)
Eve can now send the triple (m, x, s) as a message with a forged signature to Bob.
This triple will be shown to pass the signature validation of the Alabbadi–Wicker
scheme. Bob follows the verification procedure to get

(x + s)H 0 = h(m, e)Ṽ + e + h(m, e)W̃ R̃H 0

= h(m, e)G̃ + e R̃R̃−1 H T
= eH T .
It is obvious that the signature (x, s) will pass the first three steps of the verification
phase. Now Bob looks at the fourth step:.
sW 0 + xW 00 + eW −R = sR−1 W −R + xW 00 + eW −R
= eW −R + h(m, e) + xỸ W −R + xW 00 + eW −R
= eW −R + h(m, e) + xW 00 + xW 00 + eW −R
= h(m, e).
So the forged signature has passed all steps of the verification and Bob will accept
the signature as a valid one (from Alice).
Example
As an example, Eve will now forge a signature using the Alabaddi–Wicker scheme.
The same [6, 3, 3]–code that Alabbadi and Wicker chose for their example in [AW95]
will be used here. The public and private keys for their example of the scheme are:
     
1 1 0 1 1 0 0 1 1 1 0 0 1 0 1 1 0 0
G =  1 0 1 1 0 1 ,H =  1 0 1 0 1 0 ,W =  1 1 1 1 0 1 ,
1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 1 0
   
1 0 0 0 0 0 1 0 0 0 0 0
  1 1 0 0 0 0 1 1 0 0 0 0
0 1 1 0 1 0 
0
  
0 0 1 0 1 , R−1 =  0 1
 1 1 0 0
V = 0 1 0 0 0 0 ,R = 
 
1
,
1 1 1 0 1 0 0 1 0 0 1
0 0 0 0 1 0 
1
  
0 0 1 1 0 1 0 1 0 1 1
0 0 0 0 0 1 0 0 0 0 0 1
       
0 0 1 0 1 1 0 0 1 1 0 1

 0 1 1
1 1 0
 
0 1 0
 
1 0 0
 
1 1 1  1 1 1  , W 0 =  1 1 0  , W 00 =  0 0 0  .
W −R 0
       
= , H =

 0 1 0
1 1 1
 
0 1 0
 
0 0 1
 
 1 0 0   1 1 0   1 1 1   1 0 0
1 0 1 0 0 1 1 0 1 0 0 1
Suppose that Eve has recovered the parity check matrix H as described in Section
3.5.2 (or otherwise). Now she will calculate the analogous matrices R̃, G̃, W̃ and Ỹ
from the public keys of the Alabbadi–Wicker scheme.
First Eve calculates R̃−1 from Equation (3.7):
 
1 0 0 0 0 0
0 1 0 0 1 1
 
−1
0 1 1 1 0 0
R̃ =   .
1 0 1 0 1 0

0 0 1 0 0 0
0 0 0 0 0 1
Note that many choices are possible here since H T |W −R is not a full–rank matrix.

Now she inverts this matrix to get R̃ (note that R̃−1 is a full–rank matrix, so this
is possible).  
1 0 0 0 0 0
1 1 0 1 1 1
 
0 0 0 0 1 0
R̃ = 
 .
1 1 1 1 0 1

1 0 0 1 1 0
0 0 0 0 0 1
The matrices R̃ and R̃−1 are indeed not equal to R and R−1 . However, this does
not effect Eve’s ability to forge a signature.
Similarly, Eve calculates the analogous matrices G̃, W̃ and Ỹ from equations
(3.10), (3.11) and (3.12):
 
0 0 0 0 0 1
    0 0 0 0 1 0
1 0 0 0 1 1 0 0 0 0 1 0 
0 0 0 0 0 0

G̃ =  0 1 0 1 0 1  , W̃ =  0 0 0 1 0 0  , Ỹ =   0 0 0 0 1 1 .

0 0 1 1 1 0 0 0 0 0 1 1 
0 0 0 0 1 0

0 0 0 0 1 1
The matrix Ṽ follows from the equation G̃ = W̃ + Ṽ :

 
1 0 0 0 0 1
Ṽ =  0 1 0 0 0 1 .
0 0 1 1 0 1
Suppose Eve wants to sign the message m = (001) and selects the error vector
e = (000001). As in [AW95], the hash value is taken to be h(m, e) = (011).
According to Equations (3.13) and (3.14) of the forgery steps, Eve calculates the
signature pair (x, s) of the message m as x = (101111) and s = (111100).
The verification of this signature pair goes as follows: in the first step, x + s =
(010011). Then the syndrome is calculated to be (010011)H 0 = (001) in the second
step. Now suppose that Bob is able to recover the error vector from the above
syndrome. Clearly, the recovered error vector will be e = (000001), since the last
column of H is exactly (001)T . Finally, the expression
sW 0 + xW 00 + eW −R = (111100)W 0 + (101111)W 00 + (000001)W −R

= (111) + (001) + (101) = (011).

Clearly, this is equal to h (001), (000001) , and Bob will accept the signature as
valid.
3.5.3 Cryptanalyzing the modified Alabbadi–Wicker scheme

Since the error vector f is not revealed to Bob, and thus also remains hidden
from Eve, the recovery of H is no longer feasible. However, a universal forgery is
still possible. Eve should first construct an analogous (non-degenerate) matrix R̃
by finding a solution to the equation
R̃W 0 = W −R .
Then she should find analogous matrices W̃ and Ỹ as described in Section 3.5.2.
Suppose Eve wants to forge a signature of the message m. To that end, she picks
a random e of weight w(e) = t0 , and then calculates a solution f to the equation
eHΓT = f R̃H 0 directly. Note that a solution always exists, since all syndromes are
taken by the vectors in Fn2 . Since this means solving a system of k linear equations
for n variables, it is possible to do this effectively. Note that HΓ is effectively public,
since both G(z) and the order of coordinates {γi } of F2m are public. She then sets
x = (e + f + h(m, e)W̃ + xY )R̃.
s = (e + h(m, e)W̃ + xY )R̃.

Bob will accept this pair as a valid signature of m, since it passes the second step
of the verification procedure:
(x + s)H 0 = (e + f + h(m, e)W̃ + xY + e + h(m, e)W̃ + xY )R̃H 0

= f R̃H 0 = eHΓT ,
as well as the last step of the verification:
sW 0 + xW 00 + eW −R = (e + h(m, e)W̃ + xY )R̃W 0 + xW 00 + eW −R

= eW −R + h(m, e)W̃ W −R + xY W −R + xW 00 + eW −R
= h(m, e) + xW 00 + xW 00 = h(m, e).
3.6 Discussion 35
Thus Eve can construct a signature for any message m. Note that this (second)
universal forgery can be slightly adapted to apply to the unmodified Alabbadi–
Wicker scheme as well, given that the decoding step in the verification is made
possible.
3.6 Discussion
The above universal forgery makes use of analogous matrices such as G̃, W̃ and
Ỹ . There are other possible drawbacks of the Alabbadi–Wicker scheme which shall
not be discussed here. The aim of this discussion is to find the reason behind the
above universal forgery. This may help to improve the Alabbadi–Wicker scheme or
design new signature schemes using error–correcting codes.
From the description of the universal forgery attack, it seems very difficult to
prevent this kind of forgery. The designers of the scheme were hoping to hide the
real secret key G between its analogous matrices using the simple fact that there are
many analogous matrices. Thus it will be infeasible for Eve to find the original map
between the message and signature, which is defined by the secret key G. However,
they did not realize that Bob does not have the ability to check this original map
between the message and its signature. Even though the analogous matrices G̃, W̃
and Ỹ define a different map, Bob cannot detect it because he does not know the
secret key.
In addition, the universal forgery in Section 3.5.2 also shows that neither the
Alabbadi–Wicker scheme nor the Xinmei scheme have the important property that it
should be infeasible for Eve to find a signature algorithm that passes the verification
step given only this verification algorithm and the public keys. In fact, there are
many such signature algorithms she can come up with. It is very difficult for the
designer to defeat them when he designs a digital signature scheme using the same
method as the Xinmei scheme.
Up to now all attempts to design a secure digital signature scheme based in
this way on error–correcting codes have failed. Why is it so hard to design such
a scheme? This is because these signature schemes do not really depend on the
hardness of the decoding problem of general error–correcting codes.
Van Tilburg [Til94] showed that signature schemes, where the security is based
only on the bounded, hard–decision decoding problem for linear codes, do not exist.
However Kabatianskii, Krouk and Smeets proposed a digital signature scheme based
on random error–correcting codes in 1997 [KKS97]. They exploited a hardly known
fact that for every linear code the set of its correctable syndromes contains a linear
subspace of relatively large dimension L. Unfortunately their scheme can only be
used once. Even so, it does give some new ideas to further explore the use of this
intractability feature of the decoding problem.
3.7 Conclusion
In this chapter the security of digital signature schemes based on error–correcting

codes was discussed and some existing weaknesses in the Xinmei scheme were sur-
veyed. Potential threats from matrices that have the same properties as some of the
secret matrices, so–called analogous matrices, were explored as well. As an example
a universal forgery of the Alabbadi–Wicker scheme was presented.
Chapter 4
Two families of Mersenne–like

primes
Summary. In this chapter two families of numbers are introduced which can
efficiently be tested for primality. These families naturally extend the Mersenne
numbers to the area of elliptic curves. The first few primes in these families are
also presented and compared to the generalized Wagstaff conjecture. This chapter
is based on joint work with Peter Beelen [BD03].
4.1 Introduction
Two families of prime numbers, not unlike the Mersenne primes, for which an
efficient primality test exists, will be studied in this chapter. For one of these families
a primality test which is as fast as the test for Mersenne numbers is presented. For
Mersenne numbers this test has led to the discovery of very big primes. In fact, the
largest explicitly known prime number at this moment (April 2003) is a Mersenne
prime. For a list of large known prime numbers see [YC03].
4.2 Testing for primality

In this section some known results concerning primality testing will be reviewed.
For an exposition of these and other tests see e.g. [Rib96].
Proposition 4.2.1 (Proth) Let n be√an odd natural number and suppose that n −
1 = 2e R, where R is odd and less than n. If a number a exists such that a(n−1)/2 ≡
−1 (mod n), then n is a prime.
Proof: Let p be the smallest prime divisor of n and let b be the order of a (mod p).
Thus b is a divisor of p − 1. Since a(n−1)/2 ≡ −1 (mod n) the greatest common
divisor of n and a(n−1)/2 − 1 is equal to one. Thus the greatest common divisor
of p and a(n−1)/2 − 1 must also be equal to one. But ab ≡ 1 (mod p), and since
37
38 Two families of Mersenne–like primes
a(n−1)/2 6≡ 1 (mod n), b cannot divide (n − 1)/2 = 2e−1 R. Since an−1 ≡ 1 (mod n),
b divides n − 1 = 2e R. The√conclusion is that 2e divides b and hence that 2e divides
p − 1. Thus p ≥ 2e + 1 > n and a contradiction arises. So one can conclude that
n has no prime factors. u
t
Proth’s test can be extended:
Theorem 4.2.2 ([HW79, Theorem 102]) Let n = 2e R + 1 with e ≥ 2 and R <

2e . Furthermore, let n satisfy ( np ) = −1 for some odd number p. Then a necessary
and sufficient condition for n to be prime is that p(n−1)/2 ≡ −1 (mod n).
Proof: If n is prime, then p(n−1)/2 (mod n) ≡ ( np ) = −1 per definition of the

Jacobi symbol. Since
√ √ p
n= 2e R + 1 > R2 + 1 > R,
the other half of the theorem follows directly from Proposition (4.2.1). u
t
Note that Hardy and Wright state a slightly different version of this theorem.
They only look at odd prime numbers p. Here the Jacobi symbol is used, which
coincides with the Legendre symbol if p is a prime.
More general than Proth’s test is the following well-known theorem:
Theorem 4.2.3 (Pocklington) Let n be a natural number and suppose that n −

e1 ek
1 = F R, where F has known prime √ factorization F = p1 · · · pk and where R is
relatively prime to F and less than n. If for each 1 ≤ i ≤ k there exists a number
(n−1)/pi
ai such that an−1
i ≡ 1 (mod n) and gcd(ai − 1, n) = 1, then n is a prime.
Proof: The proof follows directly from the proof of Proposition 4.2.1 and the
Chinese remainder theorem. u
t
Mersenne numbers are numbers of the form Mn = 2n − 1. It is easy to see that

n
2 − 1 can only be a prime if the exponent n is a prime. One of the nice things
about Mersenne prime numbers is that there exists a very efficient primality test
for them, namely the Lucas-Lehmer primality test. See for example [Rib96, page
92] or [Bre89, page 27]. The test is described in the following proposition for later
reference.
Proposition 4.2.4 Consider the Lucas sequence {Vn (2, −2)} (the indices (2,-2)
will be omitted from now on) defined recursively by V0 = 2, V1 = 2 and Vj+1 =
2Vj + 2Vj−1 . Now Mn is prime if and only if Mn divides V(Mn +1)/2 .
A proof of this proposition can be found in either of the aforementioned refer-

ences.
4.3 Prime-generating elliptic curves 39
4.3 Prime-generating elliptic curves
Let e ≥ 1 be a natural number and E an elliptic curve defined over a finite field
Fq . The curve E over the extension field Fqe will also be considered. More precisely,
denote by E(Fqe ) the group of those points of E whose coordinates are contained in
the field Fqe , and denote by Ee the cardinality of this group. The following theorem
by Hasse and Weil gives some information about these numbers.
Theorem 4.3.1 (Hasse-Weil) There exists an algebraic integer α, depending on

√
the elliptic curve E, with absolute value q such that the cardinality Ee of E(Fqe )
satisfies
Ee = q e + 1 − (αe + αe )
for all natural numbers e ≥ 1. This α is called a Frobenius eigenvalue of the elliptic
curve E.
For a proof of this theorem, see for example page 134 of [Sil86]. Note that E(Fq ) is
a subgroup of E(Fqe ). Hence E1 divides Ee for all e.
Definition 4.3.2 Let E be an elliptic curve defined over a finite field Fq . A prime-
generating elliptic curve is a curve E such that there exist infinitely many prime
numbers of the form Ee /E1 .
It is unfortunately not known whether or not there exist prime-generating elliptic

curves, but some good candidates will be given later. First, the possible values of e
for which Ee /E1 can be prime will be narrowed down.
Proposition 4.3.3 Let E be an elliptic curve defined over a finite field Fq . Suppose
that Ee /E1 is a prime. Then one of the following statements holds:
(i) e is prime,
(ii) q = 2 and e ∈ {4, 6, 9}1 ,
(iii) q = 3 and e = 4.
Proof: Suppose that e is not a prime and let f be a non-trivial divisor of e. Then
Fqf is a non-trivial subfield of Fqe . Hence E(Fqf ) is a subgroup of E(Fqe ), which
implies that Ef /E1 divides Ee /E1 . The remaining problem is to show that, except
for the last two cases mentioned in the proposition, this is a non-trivial divisor of
Ee /E1 .
Since f is a non-trivial
√ divisor of e, it can be assumed without loss of generality
that f satisfies d e e ≤ f ≤ e/2. Here df e denotes the ceiling function applied to
f . Hence, if either q ≥ 3 or e ≥ 5,
p p √
Ef ≤ ( q f + 1)2 ≤ ( q e/2 + 1)2 < ( q e − 1)2 ≤ Ee .
1 In [Kob01] two of these cases are missing.
To obtain the first and the last inequality, Hasse-Weil’s theorem was used. If q = 2
and e = 4, the strict inequality becomes an equality. So for q = 2 either E2 < E4
or E2 = E4 = 9.
Now the case Ef /E1 = 1 will be investigated. The relation
√ p
E1 ≤ ( q + 1)2 < ( q f − 1)2 ≤ Ef ,
holds whenever q = 2 and √ e > 9, or q = 3 and e > 4, or q = 4 and e > 4, or q ≥ 5.

Here the relation f ≥ d e e is used. Note that for q = 2 and e = 8 strict inequality
holds as well, since in this case f = 4.
So far it has been proven that Ef /E1 is a non-trivial divisor of Ee /E1 whenever
q = 2 and e 6∈ {4, 6, 9}, or q = 3 and e 6= 4, or q = 4 and e 6= 4, or q ≥ 5.
The case q = 4 and e = 4 still has to be excluded. For E2 /E1 to be a trivial
divisor of E4 /E1 , a curve with E1 = E2 is necessary. It is not hard to see that in
this case α = −2 (from Hasse-Weil’s theorem), and hence E4 /E1 = 25, which is not
a prime. u
t
Note that all of the above cases actually occur, as will be shown in Table 4.2 for
q = 2. Further note that it is not true that whenever e is a prime the number Ee /E1
is a prime as well. The situation is similar to the case of the Mersenne numbers.
Not all elliptic curves are prime-generating, as is shown in the following example.
Example 4.3.4 Consider the curve defined over F4 having equation Y 2 + Y =

X 3 + ϑ, where ϑ is a primitive element of F4 . In this case E1 = 1 and hence α = 2.
Ee
This implies E1
= (2e − 1)2 , which obviously never is a prime number.
Up to isomorphism there exist exactly 5 elliptic curves defined over F2 . As a

matter of fact their isomorphism classes can be characterized by E1 , the number
of points defined over F2 . From Hasse-Weil’s theorem the relation 1 ≤ E1 ≤ 5
immediately follows. In Table 4.1 representatives of these isomorphism classes E
and their Frobenius eigenvalues α will be listed.
E1 Weierstrass equation of E α
1 Y 2 + Y = X3 + X + 1 √ i
1 ±
2 Y 2 + XY = X 3 + X + 1 1/2 ± i 7/2
√
3 Y 2 + Y = X3 ±i
√ 2
4 Y 2 + XY = X 3 + 1 −1/2 ± i 7/2
5 Y 2 + Y = X3 + X −1 ± i
Table 4.1: The non-isomorphic elliptic curves over F2 .
For which values of e the number Ee /E1 is a (probable) prime has been in-
vestigated for these five curves. Probable prime means that the number passed
two probabilistic primality tests: both the Mathematica function PrimeQ and the
quadratic Frobenius test as introduced in [Gra01]. The results will be listed in Table
4.2. This table extends the table given in [Kob01] for the five curves defined over
F2 .
4.4 A primality test for certain elliptic curves 41
Whether Ee /E1 is a (probable) prime has been checked for all values of e less
than or equal to 17389. Since the characteristic is 2, the only candidates for e are
prime numbers and the numbers in the set {4, 6, 9} (see Proposition 4.3.3).
The case E1 = 1 will be examined more closely in the next section.
E1 e
1 2, 3, 5, 7, 11, 19, 29, 47, 73, 79, 113, 151, 157, 163, 167, 239, 241, 283, 353, 367,
379, 457, 997, 1367, 3041, 10141, 14699
2 2, 3, 5, 7, 11, 17, 19, 23, 101, 107, 109, 113, 163, 283, 311, 331, 347, 359, 701,
1153, 1597, 1621, 2063, 2437, 2909, 3319, 6011, 12829
3 2, 3, 4, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347,
701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479
4 2, 5, 7, 9, 13, 19, 23, 41, 83, 97, 103, 107, 131, 233, 239, 277, 283, 349, 409, 571, 1249,
1913, 2221, 2647, 3169, 3527, 4349, 5333, 5903, 5923, 6701, 9127, 9829, 16187
5 4, 5, 6, 7, 9, 11, 13, 17, 29, 43, 53, 89, 283, 557, 563, 613, 691, 1223, 2731, 5147,
5323, 5479, 9533, 10771, 11257, 11519, 12583
Table 4.2: All e ≤ 17389 for which Ee /E1 is a (probable) prime.
4.4 A primality test for certain elliptic curves
If either N + 1 or N − 1 can be factored, there exists an efficient way of testing

N for primality. The numbers which will be tested have the form Ee /E1 , where E1
is some small number and Ee = q e + 1 − (αe + αe ) for some complex number α of
√
absolute value q. In general there seems no hope to factor Ee /E1 ± 1, since the
nice structure of the number Ee is lost by the division by E1 . However, for some
elliptic curves E1 is equal to 1. In the following proposition all elliptic curves with
E1 = 1 will be given.
Proposition 4.4.1 Let E be an elliptic curve defined over Fq with the property that
E1 = 1. Then there are three possibilities:
(i) q = 2 and the curve E is isomorphic to the curve with Weierstrass equation
Y 2 + Y = X 3 + X + 1,
(ii) q = 3 and the curve E is isomorphic to the curve with Weierstrass equation
Y 2 = X 3 − X − 1,
(iii) q = 4 and the curve E is isomorphic to the curve with Weierstrass equation
Y 2 + Y = X 3 + ϑ, where ϑ is a primitive element of F4 .
This is a well-known fact from the theory of elliptic curves. As a matter of fact
all curves defined over a finite field Fq whose Jacobians have exactly one Fq -rational
point have been classified (see for example [LMQ75]). Nevertheless, the proof of the
above proposition will be given for the reader’s convenience.
Proof: First, the possible Frobenius eigenvalues α are determined. Write

α = a + bi, with a and b real numbers. Then the relation a2 + b2 = q holds
by Hasse-Weil’s theorem. Further, the assumption E1 = 1 implies the equation
a = q/2. Hence b2 = q − q 2 /4. Since b2 ≥ 0, this implies q ∈ {2, 3, 4}. This gives
rise to the three cases mentioned in the proposition. u
t
Note that for all of the three cases mentioned above, α + α = q, so the three
curves are supersingular. We shall now determine the numbers Ee for these three
cases.
Proposition 4.4.2 Let E be the elliptic curve defined over F2 with Weierstrass
equation Y 2 + Y = X 3 + X + 1. Then the Frobenius eigenvalues are given by 1 ± i.
Furthermore
 e

 2 − 2e/2+1 + 1 if e≡0 (mod 8),
 e
 2 − 2(e+1)/2 + 1
 if e ≡ 1, 7 (mod 8),
Ee = 2e + 1 if e ≡ 2, 6 (mod 8),
2e + 2(e+1)/2 + 1 if e ≡ 3, 5 (mod 8),




 e
2 + 2e/2+1 + 1 if e≡4 (mod 8).
Let E be the elliptic curve defined over F3 with Weierstrass

√ equation Y 2 = X 3 −X−1.
Then the Frobenius eigenvalues are given by (3 ± i 3)/2 and
 e
 3 − 2 · 3e/2 + 1 if e≡0 (mod 12),
 3e − 3(e+1)/2 + 1



 if e ≡ 1, 11 (mod 12),
 3e − 3e/2 + 1

 if e ≡ 2, 10 (mod 12),
Ee = 3e + 1 if e ≡ 3, 9 (mod 12),
3e + 3e/2 + 1 if e ≡ 4, 8 (mod 12),




3e + 3(e+1)/2 + 1 if e ≡ 5, 7 (mod 12),




 e
3 + 2 · 3e/2 + 1 if e≡6 (mod 12).
Let E be the elliptic curve defined over F4 with Weierstrass equation Y 2 +Y = X 3 +ϑ,
where ϑ is a primitive element of F4 . Then the Frobenius eigenvalue is given by 2
and the number of F4 -rational points satisfies
Ee = 4e − 4(e+1)/2 + 1 = (2e − 1)2 .
Proof: The results follow directly from Theorem 4.3.1. u

t
The third curve can never give (new) primes, since Ee is the square of a Mersenne
number for any e (see Example 4.3.4). For the first two curves the following corollary
is stated:
Corollary 4.4.3 Let e be a prime not equal to 2 or 3. Then Ee = 2e − 2e 2(e+1)/2 +

1 for the firstcurve in Proposition 4.4.2. Forthe second curve in Proposition 4.4.2,
Ee = 3e − 3e 3(e+1)/2 + 1. Here 2e and 3e denote Legendre symbols.

4.4 A primality test for certain elliptic curves 43
These numbers can be viewed as an equivalent of Mersenne numbers in the ring

of Gaussian (respectively Eisenstein) integers, hence the following names:
Definition 4.4.4 Let e be an odd prime. Define the Gauss-Mersenne number GMe
as

2 e
GMe = 2 − 2(e+1)/2 + 1,
e
and the Eisenstein-Mersenne number EMe as

3
EMe = 3e − 3(e+1)/2 + 1.
e
For these two numbers, GMe − 1 (respectively EMe − 1) can be factored easily to
such an extent that a primality test for the numbers GMe and EMe immediately
follows:
Theorem 4.4.5 Let e be an odd prime and n ≥ 2. Define


3 if e ≡ 5, 7 (mod 8),
a= 5 if e ≡ 3 (mod 8),
 2n
2 +1 if e ≡ 2n+1 + 1 (mod 2n+2 ).
The number GMe is a prime if and only if
a(GMe −1)/2 ≡ −1 (mod GMe ).
Proof: According to Theorem 4.2.2, the only thing that has to be shown is that
GM

a
e
= −1. However, this follows immediately by repeatedly using the quadratic
reciprocity law for Jacobi symbols. In the case e ≡ 7 (mod 8) we have
e+1
!
2e − 2

GMe 2 +1 3 3
= = e+1 = ,
a 3 2e − 2 2 +1 2−1+1
because if we set e = 7 + 8k we get 27+8k ≡ 27 28k ≡ 128256k ≡ 2 (mod 3) and

24+4k ≡ 24 24k ≡ 1616k ≡ 1 (mod 3). So

GMe 3
= = −1.
a 2
When e ≡ 5 (mod 8) we have

e+1
!
2e + 2

GMe 2 +1 3 3
= =− e+1 =− ,
a 3 2e + 2 2 +1 2−2+1
since writing e = 5 + 8k yields 25+8k ≡ 25 28k ≡ 32256k ≡ 5 (mod 3) and 23+4k ≡

23 24k ≡ 816k ≡ 2 (mod 3). So

GMe 3
=− = −1.
a 1
If e ≡ 3 (mod 8), the relation

e+1
!
2e + 2

GMe 2 +1 5 5
= = e+1 =
a 5 2e + 2 2 +1 3+4+1
holds, since if we write e = 3 + 8k we have 23+8k ≡ 23 28k ≡ 3256k ≡ 3 (mod 5) and

22+4k ≡ 22 24k ≡ 416k ≡ 4 (mod 5). Thus

GMe 5 3 3
= = = = −1.
a 3 5 2
Lastly, if e ≡ 1 (mod 8) there exists an integer n ≥ 1, such that e ≡ 2n+1 + 1

(mod 2n+2 ). Then
e+1
! n n
2e − 2 2 + 1 22 + 1 22 + 1

GMe
= = = = −1,
a 22n + 1 e+1
2e − 2 2 + 1 22n − 22n + 1
since e > (e + 1)/2 > 2n . u

t
To perform this primality test e squarings and 1 multiplication modulo GMe
(e−1)/2 (e+1)/2
has to be computed since a(GMe −1)/2 = (a2 a±1 )2 . Since a squaring
takes far more work than an addition, additions will be ignored in this estimate.
The modular reduction can be implemented in a few additions because of the special
form of the numbers. Therefore the computational complexity of this primality test
is O(log2 (GMe )) squarings.
Now the computational complexity of the Lucas-Lehmer test will be considered.
The primality test of Proposition 4.2.4 can be rewritten as follows:
Proposition 4.4.6 Define the sequence {sn } inductively by s1 = 4 and sn+1 =

s2n − 2. For an odd prime p the Mersenne number Mp = 2p − 1 is a prime if and
only it divides sp−1 .
Note that the two sequences sj and Vj are connected by the relation sj =
j−1
V2j /22 . This form of the Lucas-Lehmer test is easier to compute, since the calcu-
lation of sp−1 (mod Mp ) only involves p−2 squarings modulo the Mersenne number
Mp . Note that in this case the modular reduction can be done with a single addi-
tion because of the special form of the Mersenne number. Thus the computational
complexity of the Lucas-Lehmer test is O(log2 (Mp )) squarings.
Therefore it is fair to say that the test of Theorem 4.4.5 is about as efficient as
the Lucas-Lehmer test for the Mersenne primes. An actual implementation of this
4.5 The Wagstaff conjecture 45
test has revealed that Gauss-Mersenne primes exist. The number GMe is a prime
for each e in the set
{2, 3, 5, 7, 11, 19, 29, 47, 73, 79, 113, 151, 157, 163, 167, 239, 241, 283, 353, 367, 379,
457, 997, 1367, 3041, 10141, 14699, 27529, 49207, 77291, 85237}.
While we were looking for larger e, M. Oakes et al. [Oak00] found that GMe
is prime for e ∈ {106693, 160423, 203789, 364289} as well. It was shown by us that
this list is complete for e ≤ 188369. Also, no prime number GMe was found with e
in the closed interval [566000, 695566].
Now consider the Eisenstein-Mersenne numbers:
Theorem 4.4.7 The number EMe is a prime if and only if either 2(EMe −1)/3 ≡
−3e (mod EMe ) or 2(EMe −1)/3 ≡ 3e − 1 (mod EMe ).
Proof: The “if”-part follows directly from Pocklington’s theorem. To show the
“only if”-part, suppose that EMe is a prime. Note that in this case the solutions of
the equation x3 ≡ 1 (mod EMe ) are given by 1, −3e , and 3e −1. Hence all that√
needs
to be shown is that 2 is not a cubic residue modulo EMe . Define ω = (−1 + i 3)/2
and α = 2 + ω. Using the cubic reciprocity law in the ring Z[ω] (see for example
[Cox89, pages 78-80]), it can be shown that 2 is not a cubic residue modulo EMe
(still assuming that EMe is a prime). The main fact that is used is that EMe factors
over Z[ω] as EMe = (αp − 1)(αp − 1). u
t
Using a C program it was shown that EMe is a prime for each e in the set
{2, 5, 7, 11, 17, 19, 79, 163, 193, 239, 317, 353, 659, 709, 1049, 1103, 1759, 2029, 5153,
7541, 9049, 10453, 23743, 255361}.
In order to find the last value in the list, a modified version of Chris Nash’s
OpenPFGW C++ program was used as well as our own program. This list is
complete for values of e up to 268154.
4.5 The Wagstaff conjecture
The Wagstaff conjecture for the Mersenne numbers can be generalized to the
families of numbers arising from elliptic curves discussed in the preceding paragraph.
This was done independently in [Kob01]. The Wagstaff conjecture for Mersenne
numbers is the following (see [Wag83]):
Conjecture 4.5.1 (Wagstaff ) The distribution of Mersenne primes is character-
ized by
(i) The number of Mersenne primes less than or equal to x is approximately
(eγ / log 2) log log x. (Here γ is Euler’s constant).
(ii) The expected number of Mersenne primes 2p − 1 with p between n and 2n, is
approximately eγ .
(iii) The probability that 2p − 1 is prime, is approximately (eγ log ap)/p log 2 where
a = 2 if p ≡ 3 (mod 4) and a = 6 if p ≡ 1 (mod 4).
Although no proof of this statement is known, it is supported by the following

heuristic argument:
Heuristic argument. First recall that Mp = 2p − 1 can only be prime if

p itself is a prime. According to the well-known prime number theorem (see for
instance [HW79, Theorem 6]), the probability that a random number r is prime is
asymptotically equal to 1/ log r. However, Mp is not a random number, and also
does not behave as such. Namely, if q divides Mp , then obviously 2p = 1 (mod q)
and the order of 2 modulo q divides the prime p, and thus must be equal to p. By
Fermat’s little theorem we have that the order of 2 modulo q divides q − 1, thus any
divisor q of Mp must be of the form q = kp + 1 where k is an integer. Also observe
that 2(q−1)/2 = 2pq = 1 (mod q), so 2 is a quadratic residue modulo q and so q must
be equal to ±1 modulo 8. Thus the smallest divisor of Mp is at least ap + 1 where
a = 2 if p is 1 modulo 4, and a = 6 if p is 3 modulo 4.
Since prime numbers q that are smaller than ap + 1 cannot divide Mp , the
1
probability that Mp is prime is enlarged by a factor of (1−1/q) for each prime q <
ap + 1. Thus an estimate of the above probability is
1 Y 1
p
,
log (2 − 1) q<2ap+1 (1 − 1/q)
where the product is taken only over prime numbers q. Merten’s theorem (see for
example [BS96]) states that
n
1 Y pi
lim = eγ ,
n→∞ log n
i=1
p i − 1
where pi is the ith prime number. Thus this probability is asymptotically equal to
(eγ log ap)/p log 2. The first two claims easily follow from this observation.
For prime-generating elliptic curves Wagstaff’s conjecture can be generalized:
Conjecture 4.5.2 Let E be a prime-generating elliptic curve defined over the field
Fq . Then the following statements can be made about the distribution of the primes
generated by E:
(i) The number of primes of the form Ek /E1 less than or equal to x, is approxi-
mately (eγ / log q) log log x.
(ii) The expected number of primes of the form Ek /E1 with k between n and qn,
is approximately eγ .
(iii) The probability that Ek /E1 is prime, is approximately eγ log ak/k log q, where
a depends on the specific choice of E (in general a = 2).
The a in the above conjecture is due to the fact that for all prime divisors d of
Ee /E1 we have d ≡ 1 (mod ae), if e is odd and q is not too large [Bee01, Theorem
4.5 The Wagstaff conjecture 47
5.3.2]. In general, a = 2 gives a sharp bound. However, for some specific curves this
bound can be improved, as is shown for the two families of Mersenne-like numbers
in the next proposition.
Proposition 4.5.3 Let e be an odd prime larger than 3. Then the following state-
ments hold:
(i) Suppose that l is a prime divisor of the number GMe = 2e − 2e 2(e+1)/2 + 1.

Then l ≡ 1 (mod 4e).

(ii) If l is a prime divisor of the number EMe = 3e − 3e 3(e+1)/2 + 1, we have

that l ≡ 1 (mod 6e).

Proof: Note that GMe is a divisor of 22e + 1. This implies that 22e ≡ −1 (mod l).
Hence the multiplicative order of 2 in the group F∗l is a divisor of 4e. This implies
after some manipulation of the formulas that the multiplicative order of 2 equals
4e. Thus l ≡ 1 (mod 4e). For the other half of the proposition, note that EMe is a
divisor of 33e + 1 and proceed analogously. u
t
Ep
logq logq n
E1
20
15
10
n
10 20 30 40
? Mersenne primes
Gauss-Mersenne primes
Eisenstein-Mersenne primes
—— Wagstaff conjecture
Figure 4.1: Generalized Wagstaff’s conjecture
Table 4.2 and the results concerning the Mersenne-like primes found in the pre-
vious section give an idea of how accurate both Wagstaff’s conjecture and its gen-
eralization are. Define pn to be the n-th number in the respective family such that
Epn /E1 is a prime and suppose that the elliptic curve is defined over Fq . Accord-
ing to Wagstaff’s conjecture the plot of n against logq (logq (Epn /E1 )) should lie
on a straight line with slope e−γ . In this way the accuracy of Conjecture 4.5.2
can be observed graphically. In Figure 4.1 a line with slope e−γ and the points
(n, log2 (log2 (GMpn ))) have been drawn. The respective points for the (currently)
known Mersenne primes Mp and the (currently) known Eisenstein-Mersenne primes
EMp are included in the figure as well.
Chapter 5
Pseudorandom sequences from

elliptic curves
Summary. In this chapter some known constructions to produce pseudorandom

sequences with the aid of elliptic curves will be generalized. Both additive and
multiplicative characters on elliptic curves will be used for this purpose. This chapter
is based on joint work with Peter Beelen [BD02].
5.1 Introduction
Nowadays, many applications call for random numbers. One of the most prefer-
able ways to generate those would be to take a monkey, give him a coin to flip, and
write down the result of each coin flip. Unfortunately this process is quite slow,
and a faster way to generate random numbers is needed. On second thought, a
sequence of numbers that appears random would be just as good - who could tell
the difference? Such a sequence will be called pseudorandom.
Many people have constructed pseudorandom number generators using many,
diverse methods (see for example [MOV97, Chapter 5] for an overview). The first
study of using linear congruences on elliptic curves to generate pseudorandom se-
quences was done in [Hal94]. Further results on these generators were obtained in
[MS02; GBS00; KS00; VW00]. Some of these constructions will be generalized here
and another construction using linear recurrence relations on elliptic curves will be
introduced. An instance of this last construction was investigated in [GL02].
5.2 Some properties of elliptic curves
As elliptic curves will be used heavily throughout this chapter, first some notation
will be fixed and some elementary properties of elliptic curves will be stated. The
algebraic closure of a field F will be denoted by F .
Definition 5.2.1 An elliptic curve E is the set of projective points in P2 satisfying
49
50 Pseudorandom sequences from elliptic curves
the Weierstrass equation F (X, Y, Z) = 0, where F is defined as
F (X, Y, Z) = Y 2 Z + a1 XY Z + a3 Y Z 2 − X 3 − a2 X 2 Z − a4 XZ 2 − a6 Z 3 .
A curve E is said to be defined over Fq if a1 , . . . , a6 ∈ Fq .
However, usually one considers the (affine) non-homogeneous equation obtained by

putting x = X/Z and y = Y /Z in the equation F (X, Y, Z) = 0:
y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,
always remembering to include the point O at infinity, which has projective coordi-
nates [0 : 1 : 0]. We will write the affine equation as f (x, y) = F (X/Z, Y /Z, 1). A
point P satisfying ∂f ∂f
∂x (P ) = ∂y (P ) = 0, will be called singular. In this chapter, we
will only consider non-singular elliptic curves, that is elliptic curves which have no
singular point(s).
Elliptic curves have an Abelian group structure [Sil86, Section 3.2]. Adding two
points P and Q is done by first taking the line through P and Q (if P = Q, take the
tangent at P ). This line will intersect the curve E in a third point R, since f is a
cubic equation. Note that points are counted with multiplicity. The sum of P and
Q is now defined to be the intersection point of the line through R and O. Scalar
multiplication of a point P on an elliptic curve by n, i.e. adding P to itself n times,
will be denoted by [n]P .
A point is called F-rational if its coordinates are in F. The group of F-rational
points (see [Sil86, page 57] for proof that these points form a group) on the curve
E will be denoted by E(F). A point P ∈ E is called a n-torsion point if it satisfies
[n]P = O. The n-torsion subgroup of E will be denoted by E[n].
The function field of an elliptic curve E defined over Fq is defined to be the
quotient field of Fq [x, y]/(f (x, y)). It will be denoted by F(C), or by Fq (C) if only
the functions with coefficients in Fq are considered. The valuation map vP (g) is a
map from F(C) to Z ∪ ∞, which takes as value minus the pole order of g at P . So if
g has a zero of degree k at point P and a pole of degree l at Q, one has vP (g) = k
and vQ (g) = −l. For every (rational) function f ∈ F(C), there are finitely many
points where vP (f ) 6= 0 [Sil86, Proposition 2.1.2].
An algebraic curve C is a projective variety of dimension 1, with an arbitrary
genus g. Elliptic curves are algebraic curves with genus g = 1. For more information
on algebraic curves, see for instance [Sil86, Chapter 2] or [Sti93].
The following famous result by Hasse and Weil concerns the number of points
of an algebraic curve. For a proof of this theorem, see for instance [Sti93, Section
5.2].
Theorem 5.2.2 (Hasse-Weil bound) Let C be an algebraic curve defined over
√
Fq of genus g. Then there exist α1 , . . . , αg ∈ C of length q, such that for all e ∈ N
g
X
#C(Fqe ) = q e + 1 − (αie + αei ) .
i=1
5.3 Pseudorandom sequences 51
Corollary 5.2.3 The number of points of an algebraic curve C defined over Fq of

genus g satisfies √
|#C(Fqe ) − q e − 1| ≤ 2g q e .
Proof: This follows easily from Theorem 5.2.2. u

t
In the case of an elliptic curve, we have
Corollary 5.2.4 The number of points of an elliptic curve E defined over Fq sat-
isfies √
|#C(Fqe ) − q e − 1| ≤ 2 q e .
Proof: This follows easily from Theorem 5.2.2 and the fact that the genus of an
elliptic curve is 1. t
u
For the following proposition, see [Sil86, page 145].
Proposition 5.2.5 Let E be an elliptic curve defined over the finite field Fq . Then
there exist numbers k and l such that the elliptic curve as an Abelian group satisfies
E(Fq ) ∼
= Z/kZ × Z/klZ.
Furthermore, k divides (q − 1).
The k and l from the above proposition will be denoted by k(E) and l(E) respectively
or by k(E, Fq ) and l(E, Fq ) if the field of definition is not immediately clear. Note
that if k = 1, the elliptic curve will have a cyclic structure.
Since k = k(E, Fq ) divides q − 1, the map from E to E obtained by multiplying
with k, is of degree k 2 and unramified, i.e. the equation [k]P = Q has k solutions
for any point Q. Further note that E[k] ⊂ E(Fq ).
5.3 Pseudorandom sequences

In this section some basic definitions concerning pseudorandom sequences are
given. First a very handy tool is introduced:
Definition 5.3.1 The trace map TrFqe |Fq is a function from Fqe to Fq defined by
2 e−1
TrFqe |Fq (x) = x + xq + xq + · · · + xq .
Note that the trace map is Fq –linear, since (a+b)q = aq +bq in Fqe , and (αa)q = αaq
for α ∈ Fq and a ∈ Fqe .
Now, some basic properties concerning pseudorandom sequences are discussed.
Definition 5.3.2 Let S = {s(0), s(1), . . . , s(N − 1)} be a sequence of elements of

Fq and let α ∈ F∗q . Denote the characteristic of Fq by p. The balance of S with
respect to α is defined in the following way:
N −1
1 X TrFq |Fp (αs(i))
BS (α) = ζp ,
N i=0
where ζp is the pth root of unity exp(2πi/p). Furthermore, the balance of S is defined
as
BS = max∗ {|BS (α)|}.
α∈Fq
Note that for binary sequences, this definition is equivalent to

N −1
1 X 1
(−1)s(i) =

BS = #{i : s(i) = 0} − #{i : s(i) = 1} .
N i=0 N
Thus the balance is a measure of any bias in the sequence S. Also, if s(i) takes
every value in Fq equally often, then BS = BS (α) = 0 for any α.
Now a similar concept for sequences defined over Z/mZ is introduced. It will be
assumed that m divides q−1. Then it is possible to identify Z/mZ with (F∗q )(q−1)/m .
Thus there exists a surjective homomorphism of groups χm : F∗q → Z/mZ.
Definition 5.3.3 If S = {s(0), s(1), . . . , s(N − 1)} is a sequence of elements of

(F∗q )(q−1)/m , then the balance with respect to α is defined as
N −1
1 X χm (αs(i))
BS (α) = ζ ,
N i=0 m
with α ∈ F∗q and ζm = exp(2πi/m).
Now the autocorrelation of a sequence can be defined in s similar way.
Definition 5.3.4 Let {s(0), s(1), . . . , s(N − 1)} be a sequence S of period N defined
over the finite field Fq . Write p for the characteristic of this field. Furthermore, let
α, β ∈ F∗q .
The autocorrelation of S with respect to α and β is defined as:
N −1
1 X TrFq |Fp (αs(i+d)−βs(i))
CS (d, α, β) = ζp ,
N i=0
with 0 ≤ d < N and ζp = exp(2πi/p). For a sequence S defined over (F∗q )(q−1)/m
the definition is
N −1
1 X χm (αs(i+d)−βs(i))
CS (d, α, β) = ζ ,
N i=0 m
with ζm = exp(2πi/m).
5.4 Using additive characters 53
Note that in the above definition i + d should be read modulo N . Also note that
for binary sequences this definition amounts to
N −1
1 X
CS (d) = (−1)s(i+d)+s(i) ,
N i=0
which is the usual definition of the autocorrelation (see for example [MOV97, Section
5.4]).
Another useful object is the crosscorrelation of two sequences:
Definition 5.3.5 Let S = {s(i)} and T = {t(i)} be two sequences defined over Fq
having the same period N . Denote the characteristic of Fq by p and let α, β ∈ F∗q .
The crosscorrelation of S and T with respect to α and β is defined as
N −1
1 X TrFq |Fp (αs(i+d)−βt(i))
CS,T (d, α, β) = ζp ,
N i=0
with ζp = exp(2πi/p) and 0 ≤ d < N . For sequences S and T defined over

(F∗q )(q−1)/m the crosscorrelation is defined as
N −1
1 X χm (αs(i+d)−βt(i))
CS,T (d, α, β) = ζ ,
N i=0 m
Note that the crosscorrelation CS,S (d, α, β) of a sequence with itself is equal to
the autocorrelation CS (d, α, β), as it should be.
The problem is to find a family of sequences Σ = {Si |i ∈ I} such that for all
i, j ∈ I the crosscorrelations CSi ,Sj (d, α, β) are small. Such a family of sequences
could be used for CDMA purposes, for instance in mobile telephony. Also, the
autocorrelation of a sequence obtained by concatenating two or more sequences
from such a family is essentially bounded by these crosscorrelations. When the
generator has to switch to another member of the family, one would still want
certain properties to hold for the autocorrelation of its combined output.
5.4 Using additive characters
Some generalizations of known constructions of pseudorandom sequences from

elliptic curves will be given in this section.
Let E be an elliptic curve defined over a finite field Fqe of characteristic p. Sup-
pose for now that this group is cyclic of order N = l(E) (i.e. k(E) = 1) and has
generator P . Let f ∈ Fqe (E) be a function on E defined over Fqe . The pseudoran-
dom sequence S = {s(i)} will be studied in this section, where the s(i) are given
by:
s(i) = TrFqe |Fq (f ([i]P )),

with 0 ≤ i < N .
The condition that E(Fqe ) is a cyclic group is a natural one, since an ordering
of the points in E(Fqe ) is needed. In the literature this assumption is often made.
Moreover, the field Fq is usually assumed to be Fp . Both these restrictions will be
removed in this section. First some concepts are introduced.
Definition 5.4.1 Let C be an algebraic curve of genus g defined over Fq . Let f ∈

Fq (C) be a rational function on C defined over Fq as well. Define C AS (f, Fq ) to be
the set of all Fq -rational points Q on C such that there exists a function g ∈ Fq (C)
(depending on Q) with the property that f − g p + g is defined at Q.
Here g p denotes taking the pth power of each function value, so that Tr(g p − g) =
0. Note that for every function f ∈ Fq (C) and point Q ∈ C(Fq ) there exists a
function g ∈ Fq (C) such that either vQ (f − g p + g) ≥ 0 or vQ (f − g p + g) < 0 and
p 6 |vQ (f − g p + g). Define mQ = −1 in the former case and mQ = −vQ (f − g p + g)
in the latter. Of course mQ depends on f as well. When this is to be made explicit
mQ (f ) will be written instead of mQ . For more details see [Sti93, page 114].
Also observe that the quantity TrFq |Fp ((f − g p + g)(Q)) does not depend on g as
long as the function f − g p + g is defined at Q. Thus, even if f itself is not defined
in Q, the notation TrFq |Fp (f (Q)) will be used for Q ∈ C AS (f, Fq ).
Now define the sequence to be studied is given by:
Definition 5.4.2 Let E be an elliptic curve defined over Fqe . Suppose that P is a
generator of the group [k(E, Fqe )]E(Fqe ) and denote its order by N . Let f ∈ Fqe (E).
The sequence S AS (f, P ) = {s(i)}0≤i<N is defined by
s(i) = TrFqe |Fq (f ([i]P )).
Here the convention that TrFqe |Fq (f (Q)) = 0 if Q 6∈ E AS (f, Fqe ) is used. Of course
this sequence depends on the elliptic curve as well, but this is not made explicit in
the notation.
Note that in the above notation N = l(E, Fqe ) and that if E(Fqe ) is cyclic, the
situation has already been studied in the literature [GBS00; VW00].
From the point of view of coding theory an ordering of the points in E(Fqe ) is
unnecessary. In this case any change of ordering gives rise to an equivalent code.
Indeed there is in that case no need of restricting oneself to elliptic curves. The
resulting codes are called trace-codes. They have been studied in for example [Sti93,
Chapter 8] and [Vos93].
Before some estimates for the parameters of the pseudorandom sequences de-
fined above are given, some more theory is needed. The key to the results is the
proposition about the following exponential sum:
Definition 5.4.3 Let C be an algebraic curve defined over Fq . Let f ∈ Fq (C). Now
look at the following exponential sum:
X TrFq |Fp (f (P ))
ES AS (C, f ) = ζp ,
P ∈C AS (f,Fq )
with ζp = exp(2πi/p).
A known upper bound for this exponential sum is given in the next proposition.
Proposition 5.4.4 Let C be an algebraic curve of genus g defined over Fq . Let

f ∈ Fq (C) and suppose that f 6= z p − z for all z ∈ F(C). Then the following holds:
 
AS
ES (C, f ) ≤ 2g − 2 +
X √
(mP + 1) q.
P ∈C(Fq )
This proposition was proven in [Bom66; KS00; VW00]. The gist of the proof is
given here for the convenience of the reader.
Proof: The proposition can be rephrased by considering the curve D, defined over
Fq whose function field is given by Fq (C)(z) with z p − z = f . Denote its genus by h.
The L-function of D is the product of the L-function of C with the following p − 1
expressions (1 ≤ i ≤ p − 1):
 
X Te X iTrFqe |Fp (P )
exp  ζp .
e AS
e≥1 P ∈C (f,Fqe )
As a matter of fact the above expressions turn out to be polynomials. By Hasse-

√
Weil’s theorem these polynomials have roots of length 1/ q and hence for all e ≥ 1
the following relation holds.

√

≤ 2(h − g) q e .
X TrFqe |Fp (P )
ζ p

P ∈C AS (f,Fqe )

p−1
Using the theory for Artin-Schreier extensions an explicit expression for the genus h
can be derived (see for example [Sti93, Section 3.7]). This leads to the upper bound
given in the proposition. u
t
By applying the above result an estimate for the parameters of the sequences
S AS (f, P ) can now be given.
Theorem 5.4.5 Let E be an elliptic curve defined over the finite field Fqe of char-
acteristic p. Set k = k(E, Fqe ). Furthermore, let f ∈ Fqe (E) be a function and P be
a generator of the group [k]E(Fqe ).
Suppose that for all z ∈ F(E) the relation z p − z 6= f ◦ [k] holds and that
E AS (f ◦ [k], Fqe ) = [k]−1 E AS (f, Fqe ) ∩ hP i .

Then BS AS (f,P ) is bounded from above by

 
1  1 X √
N − #(E AS (f, Fqe ) ∩ hP i) + (mQ (f ◦ [k]) + 1) q e  ,
N k(E)2
Q
with N = #hP i.
Proof: Denote by S the sequence {TrFqe |Fq (f (Q))} with Q ∈ E AS (f, Fqe ) ∩ hP i.
Further denote by T the sequence {TrFqe |Fq (f ◦ [k](Q))} with Q ∈ E AS (f ◦ [k], Fqe ).
The relation E AS (f ◦ [k], Fqe ) = [k]−1 E AS (f, Fqe ) ∩ hP i holds and hence for each

point R in E AS (f, Fqe )∩hP i, there exist exactly k 2 points Q in the set E AS (f ◦[k], Fqe )
such that [k]Q = R. Thus for any α ∈ F∗q
#E AS (f ◦ [k], Fqe )BT (α) = k 2 #(E AS (f, Fqe ) ∩ hP i)BS (α).

So
BT (α) = BS (α).
Since
N · |BS AS (f,P ) (α)| ≤ N − #(E AS (f, Fqe ) ∩ hP i) + #(E AS (f, Fqe ) ∩ hP i)|BS (α)|,
an upper bound for BT (α) results in an upper bound for BS AS (f,P ) . However, since
#E AS (f ◦ [k], Fqe )BT (α) = ES AS (E, f ◦ [k]) , such an upper bound is available from
Proposition 5.4.4. This concludes the proof. u
t
Note that the technical condition
E AS (f ◦ [k], Fqe ) = [k]−1 E AS (f, Fqe ) ∩ hP i

is fulfilled if k = 1. Also note that the righthandside set is always contained in the
lefthandside set.
Now a special case of the above lemma is considered. Denote by wdeg(f (x, y))
the weighted degree of a polynomial in two variables defined by wdeg(x) = 2 and
wdeg(y) = 3. Thus the weighted degree of a polynomial is equal to the highest
weighted degree of its monomials. Note that the choice of degrees for the monomials
x and y is natural for elliptic curves, since one works modulo the polynomial f (x, y),
and thus the weighted degree of y 2 should be equal to the weighted degree of x3 for
a consistent definition.
Corollary 5.4.6 Let E be an elliptic curve defined over the finite field Fqe of char-
acteristic p given by a Weierstrass equation. Let f be a polynomial in the coordinate
functions x and y such that degy (f ) ≤ 1. Further let P be a generator of the group
[k(E)]E(Fqe ) and define N = #hP i. Suppose that p does not divide wdeg(f ). Then
1 √
BS AS (f,P ) ≤ 1 + (1 + wdeg(f )) q e .
N
Note that the above corollary also follows from [KS00, Theorem 1] or the work
of Bombieri [Bom66]. The condition degy (f ) ≤ 1 is not a real restriction, because
the Weierstrass equation can be used to reduce this degree if degy (f ) ≥ 2. Further
note that if this condition is met, the relation vO (f ) = −wdeg(f ) holds where O is
the point at infinity [0 : 1 : 0]. For the proof of the above theorem one uses that
E AS (f, Fqe ) = E(Fqe ) \ {O} and that E AS (f ◦ [k(E)], Fqe ) = E(Fqe ) \ E[k(E)].
In the same way the autocorrelation of the sequences S AS (f, P ) can be investi-
gated. Before moving to the main theorem on this, a lemma is stated.
Lemma 5.4.7 Let E be an elliptic curve defined over the field Fqe of characteristic
p. Let f ∈ Fqe (E) and choose α, β ∈ F∗q . Write k = k(E, Fqe ) and choose a generator
P of the group [k]E(Fqe ) and a number d satisfying 1 ≤ d < N with N = #hP i.
Define h ∈ Fqe (E) by
h(X) = αf (X ⊕ [d]P ) − βf (X).

Denote by S the sequence {TrFqe |Fp (h ◦ [k](Q))} with Q ∈ E AS (h ◦ [k], Fqe ). Finally
suppose that E AS (h ◦ [k], Fqe ) = [k]−1 E AS (h, Fqe ) ∩ hP i . Then

N · CS AS (f,P ) (d, α, β) = c + #(E AS (h, Fqe ) ∩ hP i)BS .

Here
X TrFqe |Fp (h(Q))
c= ζp ,
Q
where the sum is over points Q such that Q ∈ hP i and Q 6∈ E AS (h, Fqe ).
Proof: Note that CS AS (f,P ) (d, α, β) = BS AS (h,P ) (1). Using similar techniques as
in the proof of Lemma 5.4.5, the result is obtained. t
u
Using an upper bound for exponential sums, an upper bound for the autocor-
relation can be derived, if some technical conditions are met. More explicitly, the
following theorem is proven in the case that f is a polynomial in the coordinate
functions.
Theorem 5.4.8 Let E be an elliptic curve defined over the field Fqe given by a
Weierstrass equation. Let f be a polynomial in the two coordinate functions x and
y, such that degy (f ) ≤ 1. Choose α, β ∈ F∗q . Further choose a generator P of the
group [k(E)]E(Fqe ) and a number d satisfying 1 ≤ d < N with N = #hP i. Suppose
that the characteristic of Fq does not divide wdeg(f ). Then the autocorrelation can
be bounded as follows:
1 √
|CS AS (f,P ) (d, α, β)| ≤ 2 + 2(1 + wdeg(f )) q e .
N
Analogously to the autocorrelation, properties about the crosscorrelations of
sequences can be derived. Some results are stated in the following theorem.
Theorem 5.4.9 Let E be an elliptic curve defined over the finite field Fqe of char-
acteristic p, given by a Weierstrass equation. Let P be a generator of the group
[k(E)]E(Fqe ) and write N = #hP i. Let f1 and f2 be two polynomials in the coor-
dinate functions x and y such that degy (fi ) ≤ 1 for i = 1, 2, and such that for all
(α, β) ∈ Fq2e \ {(0, 0)} the relation p 6 |wdeg(αf1 − βf2 ) holds. Write S1 = S AS (f1 , P )
and S2 = S AS (f2 , P ). For all α, β ∈ F∗q and 0 ≤ d < N the crosscorrelation can be
bounded as
1 √
|CS1 ,S2 (d, α, β)| ≤ 2 + (2 + wdeg(f1 ) + wdeg(f2 )) q e ,
N
unless d = 0 and αf1 = βf2 .
Proof: This is a straightforward generalization of the proof of Theorem 5.4.8. t

u
Now an example of a family of sequences having good crosscorrelations will be
given. In this example it is assumed that the characteristic is 2, since this is the
most interesting case for applications.
Example 5.4.10 Let E be an elliptic curve defined over the finite field F2e . Denote
by P a generator of the group [k(E)]E(Fqe ) and write N = #hP i. Let a be defined
by a = (a0 , · · · , am ) ∈ F2m+1
e and let Sa be the binary sequence S AS (fa , P ) with
defining function fa = a0 y + · · · + am xm y.
For any number 0 ≤ d < N and a, b ∈ Fqn+1 e \ {0} the crosscorrelation of the two
sequences can be bounded as
1
√
|CSa ,Sb (d)| ≤ 2 + (2 + wdeg(f e
N
1
√ a) + wdeg(fb )) 2
≤ e
2 + (8 + 4m) 2 ,
N
unless d = 0 and a = b.
5.5 Using multiplicative characters

Now multiplicative characters and Kummer extensions will be used to obtain
similar results as in the previous section, instead of additive characters and Artin-
Schreier extensions. Codes have been obtained using this approach in [Per91]. Se-
quences have been constructed in this way using the projective line in [Bar97]. Here
sequences will be constructed using elliptic curves.
5.5 Using multiplicative characters 59
Definition 5.5.1 Let C be an algebraic curve defined over Fq . Choose 1 < m < q−1
a divisor of q − 1 and let f ∈ Fq (C). Define C K (f, Fq ) to be the set of Fq -rational
points on C such that there exists a g ∈ Fq (C) such that vP (f · g m ) = 0.
Note that if φ : F∗q → Z/mZ is a homomorphism of groups, the quantity φ((f ·
g m )(Q)) does not depend on g, as long as vQ (f · g m ) = 0. Hence, φ(f (Q)) will be
written instead of Q ∈ C K (f, Fq ), even if vQ (f ) 6= 0. In particular the quantity
f (Q)(q−1)/m is well-defined for Q ∈ C K (f, Fq ). If Q 6∈ C K (f, Fq ), a g ∈ Fq (C) can
always be found such that (f · g m )(Q) = 0. Hence f (Q)(q−1)/m is defined to be
zero for Q 6∈ C K (f, Fq ), even if f has a pole in Q. In the same way φ(f (Q)) = 0 is
defined for Q 6∈ C K (f, Fq ).
Definition 5.5.2 Let E be an elliptic curve defined over Fq . Fix a natural number
1 < m < q − 1 dividing q − 1. Denote by χm : F∗q → Z/mZ some fixed, surjective
homomorphism of groups. Let P ∈ E(Fq ) and f ∈ Fq (E). Define S K (f, P ) = {s(i)}
by
s(i) = χm (f ([i]P )).

The homomorphism χm is needed to define the balance and correlations of the
sequence S K (f, P ) (see Section 5.3). Note that χm (f (Q)) = 0 if Q 6∈ E K (f, Fq ).
Example 5.5.3 Let Fp be a prime field with p odd. Let α be a generator of the
multiplicative group F∗p . Let f [X] be a polynomial in Fp [X] of degree m. By evaluat-
ing this polynomial in all elements α, α2 , . . . of F∗p a codeword from a Reed-Solomon
code (RS-code) is obtained. A binary sequence is obtained from this codeword by
applying the map χ2 : Fp → Z/2Z coordinatewise, defined by

 0 if a = 0 or a = 1,
p
χ2 (a) =
 1 if a = −1.
p

Here, ap denotes the Legendre symbol, which indicates whether a is a quadratic
residue modulo p. If for example p = 13, f [X] = X 2 + X and α = 2 are chosen the
codeword
(2, 6, 7, 7, 12, 3, 0, 2, 12, 4, 6, 4)

and corresponding binary sequence
(1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0)
are found.
As said before, it is possible to obtain codes using this construction. This was
done in [Per91]. There, non-linear codes were found and investigated. It is possible
to find interesting linear codes as is shown in the following example. After the
example, the study of sequences is resumed.
Example 5.5.4 Choose C to be the projective line defined over some finite field Fq
of odd characteristic. For M ⊂ Fq (x)/(Fq (x))2 the group generated by the residue
classes of x − β is chosen, with β in some non-empty subset S of Fq . Then every
element of M has a representative of the form β∈S (x − β)β with β ∈ {0, 1}. As
Q
a vector space over F2 , the group M has dimension #S. Define χ2 as in Example
5.5.3. Evaluating χ2 ◦f in the set Fq \S for all functions f ∈ M, yields a binary linear
code C of length #(Fq \S). Its dimension is less than or equal to min(#S, #(Fq \S)).
Equality need not hold in this equation. Suppose
√
for example that q is a square.
The evaluation of the polynomial f (X) = X q + X in an element a of F√q is either
zero or a square. To see this note that for a ∈ Fq the relation f (a) q = f (a)
holds, and hence√
either f (a) = 0 or f (a)(q−1)/2
√
= 1. Thus, if S is chosen to be
S = {a ∈ Fq | a + a = 0}, the polynomial X q + x will correspond to the all-zero
q
codeword. This means that in this case the dimension of the code cannot equal the
cardinality of S. √
Note that the curve given by the equation Y 2 = X q + X has the maximum
number of Fq -rational points for its genus. As a matter of fact the number of Fq -
√ √
rational points can be seen to be 2q − q + 1, while its genus equals ( q − 1)/2.
The fact that it is maximal also follows from √
the fact
√
that it can be covered by
the Hermitian curve which has equation Y q+1 = X q + X. Using the Hasse-Weil
bound and investigating the curve Y 2 = f (X), one can show that for sets S with
√
cardinality strictly smaller than q, only the zero-polynomial can give the all-zero
codeword. This means that in this case the dimension of the resulting codes equals
the cardinality of the set S.
Refining this argument, it follows that the following statement holds for the
minimum distance d of these codes:
√
q − (#S − 1)( q − 1)
d≥ − #S,
2
√
which is a non-trivial lower bound if #S < q.
In a similar way as in the previous section statements about the balance, auto-
correlation and crosscorrelation of the sequences S K (f, P ) will be given.
Definition 5.5.5 Let C be an algebraic curve defined over Fq . Let 1 < m < q − 1 be
a divisor of q − 1 and denote by χm : F∗q → Z/mZ some surjective homomorphism
of groups. Let f ∈ Fq (C). Define the following exponential sum:
X
ES K (C, f ) = χm (f (P ))
ζm ,
P ∈C K (f,F q)
For this exponential sum a bound exists similar to that of the exponential sum
defined in Definition 5.4.3. See for example [Per91], where similar upper bounds are
derived. The proof of the following proposition is analogous to that of Proposition
5.5 Using multiplicative characters 61
5.4.4. Instead of Artin-Schreier extensions, Kummer extensions are used (see for
example [Sti93, Section[3.7]).
Proposition 5.5.6 Let C be an algebraic curve of genus g defined over Fq . Let

f ∈ Fq (C) and suppose that f 6= z l for all z ∈ F(C) and all divisors l > 1 of m.
Write rP = gcd(m, vP (f )) > 0. Then the following holds:
 
K
ES (C, f ) ≤ 2g − 2 +
X r P − 1 √
(1 − ) q.
m−1
P ∈E(Fq )
The rP occurring in the above proposition are standard in the theory of Kummer
extensions. When the role of f is to be stressed, rP (f ) will be written instead.
Theorem 5.5.7 Let E be an elliptic curve defined over the finite field Fq of charac-
teristic p. Let f ∈ Fq (E) be a function and write k = k(E, Fq ). Let P be a generator
of the group [k]E(Fq ). Suppose that the polynomial T m − f ◦ [k] is absolutely irre-
ducible. Then
 
1  X rQ (f ) − 1 √ 
BS K (f,P ) ≤ N − #(E K (f, Fq ) ∩ hP i) + (1 − ) q ,
N m−1
Q
with N = #hP i.
Proof: Note that vQ (f ◦[k]) = v[k]Q (f ) and hence rQ (f ◦[k]) = r[k]Q (f ). Moreover,
note that rQ = m for Q ∈ E(Fq ), if and only if Q ∈ E K (f, Fq ). Hence it follows that
E K (f ◦ [k], Fq ) = [k]−1 E K (f, Fq ) ∩ hP i. The rest of the proof is similar to that of
Lemma 5.4.5. u
t
In the following corollary the weighted degree of a polynomial in two variables
defined by wdeg(x) = 2 and wdeg(y) = 3 is used again.
Corollary 5.5.8 Let the notation be as in the above theorem and suppose that E is
given by a Weierstrass equation. Suppose that f is a non-trivial polynomial of total
degree ∆ in the coordinate functions x and y satisfying degx (f ) ≤ 2. Suppose that
gcd(wdeg(f ), m) = 1. Then the following bound holds:
1 √
BS K (f,P ) ≤ N − #(E K (f, Fq ) ∩ hP i) + (3∆ + 1) q .
N
If (hP i \ {O}) ⊂ E K (f, Fq ) is demanded as well, the bound
1 √
BS K (f,P ) ≤ (1 + (3∆ + 1) q)
N
holds.
Proof: This follows from the above theorem by remarking that by Bézout’s
theorem (see for example [Wae40, Section 83]) f has at most 3∆ zeros on E. Further
note that the point O is the only pole f has on E. These zeros and poles are the only
points Q for which it can happen that rQ < m. Using that rQ ≥ 1 for these points
Q, the result follows. Note that rO (f ◦ [k(E)]) = rO (f ) = gcd(wdeg(f ), m) = 1.
Hence the polynomial T m − f ◦ [k(E)] is absolutely irreducible by the theory of
Kummer extensions. u
t
Note that it can be useful to rewrite f , using the equation of E, in such a form
that the total degree is minimal. This explains why the assumption degx (f ) ≤ 2 is
made instead of degy (f ) ≤ 1, as was done previously.
Now some statements about the autocorrelation and crosscorrelations of these
sequences will be given. Most of the proofs will be omitted since they are analogous
to the proofs in the Artin-Schreier case.
Theorem 5.5.9 Let E be an elliptic curve defined over the field Fq of characteristic
p. Let f ∈ Fq (E) and choose α, β ∈ F∗q . Write k = k(E, Fq ) and choose a generator
P of the group [k]E(Fq ) and a number d satisfying 1 ≤ d < N with N = #hP i.
Define h ∈ Fq (E) by
h(X) = αf (X ⊕ [d]P ) − βf (X).

Suppose that the polynomial T m − h ◦ [k] is absolutely irreducible. Then
 
1  X r Q (h) − 1 √
|CS K (f,P ) (d, α, β)| ≤ N − #(E K (h, Fq ) ∩ hP i) + (1 − ) q .
N m−1
Q
Corollary 5.5.10 Let the notation be the same as in the above theorem. Suppose
that E is given by a Weierstrass equation. Further assume that f is a non-trivial
polynomial in the coordinate functions of total degree ∆ satisfying degx (f ) ≤ 2 and
gcd(wdeg(f ), m) = 1. Then
1 √
CS K (f,P ) (d, α, β) ≤ N − #(E K (h, Fq ) ∩ hP i) + (3∆ + 3wdeg(f ) + 2) q .
N
If (hP i \ {O, [−d]P }) ⊂ E K (h, Fq ) is demanded as well, the bound
1 √
CS K (f,P ) (d, α, β) ≤ (2 + (3∆ + 3wdeg(f ) + 2) q)
N
is found.
Proof: Again Bézout’s theorem is to be used to estimate the number of zeros

of the function h. Using the addition formula (see for example [Sil86, Section
3.2]), (x, y) ⊕ (a, b) can be written as (g1 (x, y)/(x − a)2 , g2 (x, y)/(x − a)3 ) with
g1 (respectively g2 ) a polynomial in x and y of total degree less than or equal
5.6 Using linear recurrence relations on elliptic curves 63
to 2 (respectively 3). This means that αf ((x, y) ⊕ (a, b)) can be written as
k(x, y)/(x − a)wdeg(f ) with k a polynomial of total degree less than or equal to
wdeg(f ). Hence, after multiplying the rational function h with (x − a)wdeg(f ) , a
polynomial of total degree less than or equal to ∆ + wdeg(f ) is obtained. This gives
an upper bound for the total number of zeros of the function h while its poles are
O and −[d]P . The rest of the proof is analogous to the proof of Corollary 5.5.8. tu
Theorem 5.5.11 Let E be an elliptic curve defined over the finite field Fq of char-
acteristic p. Let P be a generator of the group [k(E)]E(Fq ) and write N = #hP i.
Let f1 and f2 be two functions and choose α, β ∈ F∗q as well as a natural number
0 ≤ d < N . Write S1 = S K (f1 , P ) and S2 = S K (f2 , P ). Define h ∈ Fq (E) by
h(X) = αf1 (X ⊕ [d]P ) − βf2 (X)

and suppose that the polynomial T m − h ◦ [k(E)] is absolutely irreducible. Then the
crosscorrelation is bounded by
 
1  X r Q (h) − 1 √
|CS1 ,S2 (d, α, β)| ≤ N − #(E K (h, Fq ) ∩ hP i) + (1 − ) q .
N m−1
Q
Corollary 5.5.12 Let the notation be the same as in the above theorem. Sup-
pose that E is given by a Weierstrass equation. Further assume that f1 and f2
are non-trivial polynomials in the coordinate functions of total degree ∆1 and ∆2
with ∆1 ≥ ∆2 and satisfying degx (fi ) ≤ 2 with i = 1, 2. Further suppose that
gcd(wdeg(f1 ), m) = 1 if d 6= 0 and gcd(wdeg(αf1 − βf2 ), m) = 1 if d = 0. Then
1 √
CS1 ,S2 (d, α, β) ≤ N − #(E K (h, Fq ) ∩ hP i) + (3wdeg(f1 ) + 3∆2 + 2) q .
N
If (hP i \ {O, [−d]P }) ⊂ E K (h, Fq ) holds additionally, the following bound holds:
1 √
CS1 ,S2 (d, α, β) ≤ (2 + (3∆2 + 3wdeg(f1 ) + 2) q) .
N
5.6 Using linear recurrence relations on elliptic curves

In this section the balance and the period of a family of sequences obtained by
using linear recurrence relations on the points of E will be investigated.
Suppose that G is a cyclic subgroup of E of order N generated by a point P ∈ E.
In this section, N will be assumed to be a prime number.
Let r(X) = X n + rn−1 X n−1 · · · + r0 be a monic polynomial of degree n > 1
over Z/N Z with gcd(r0 , N ) = 1 and let Ω(r, G) be the vector space over Z/N Z of
bi-infinite sequences of points in G that satisfy the linear recurrence relation with
characteristic polynomial r(X). This vector space has dimension n.
Suppose from now on that the characteristic polynomial r(X) of the recursion
is irreducible over Z/N Z. It is known from the theory of linear recurrencies (see for
example [Shp99, Chapter 7]) that if r(X) is irreducible, every sequence, apart from
the zero sequence, has the same period k(N, r). As a matter of fact k(N, r) is the
smallest positive integer k such that for every root α of r(X) the relation αk = 1
holds.
Define Ψ(r, G) to be the set of sequences Ω(r, G) modulo cyclic shifts.
Lemma 5.6.1 Every point Q ∈ G occurs the same number of times in sequences
in Ψ(r, G), i.e. the number of pairs
# {(i, ψ) | 0 ≤ i < k(N, r); ψ(i) = Q; ψ ∈ Ψ(r, G)}
is independent of the choice of Q.
Proof: Since by definition of the recursion polynomial r the greatest common
divisor of r0 and N is one and this polynomial has degree n, each sequence in
Ψ(r, G) is uniquely determined by the choice of n consecutive points. Conversely,
each n-tuple of points occurs exactly once in Ψ(r, G) (note that this is modulo cyclic
shifts). Since each point Q occurs equally often in the set of all n-tuples of points,
this is the case in Ψ(r, G) as well. u
t
Let f ∈ Fqe be a function on E. Now look at the sequence S AS (f, P ) which was
defined earlier by
S AS (f, P ) = TrFqe |Fq (f ([i]P )) 0≤i<N .

Furthermore, define the set of sequences Ψf (r, G) by applying the function f to each
point in each sequence in Ψ(r, G), and then taking the trace to the ground field Fq
of the result:
Ψf (r, G) = TrFqe |Fq (f (ψ)) |ψ ∈ Ψ(r, G) .
Note that each sequence of points in Ψ(r, G) corresponds with a sequence in Ψf (r, G).
Here, the same convention as before is used, namely that TrFqe |Fq (f (Q)) = 0 if
Q 6∈ E AS (f, Fqe ).
Theorem 5.6.2 Choose a point P ∈ E. Let G be the subgroup of E generated
by P and suppose that its order is a prime N . Furthermore, let r be a monic
recursion polynomial of degree n whose zeroth coefficient is coprime to N . Then the
average balance of a sequence in Ψf (r, G) is the same as the balance of the sequence
S AS (f, P ).
Proof: Start by defining the sequence T by merging all sequences of Ψf (r, G).
Since the order of points is not important in the definition of balance and because
according to Lemma 5.6.1 each point occurs an equal number of times, we can
reorder the points of T such that we get a number of copies of the sequence
S AS (f, P ). Of course, this is the same sequence as S AS (f, P ) itself. Thus the
average balance of sequences in Ψf (r, G) is equal to the balance of the sequence
S AS (f, P ). u
t
5.7 Conclusion 65
It is well known from the theory of linear recurrencies that the period of a
sequence can be larger than the group order. So sequences defined in the above way
can have a larger period than the sequences described in the previous sections. But
this only applies to the sequences of points on E. The next theorem links this period
to the period of the generated pseudorandom sequence. The polynomial r(X) is still
supposed to be irreducible.
Theorem 5.6.3 Let r and G be defined as in the above theorem. Suppose that the
order of G is a prime N and that the degree of the recursion polynomial is n. Denote
by Tf (a) the number of points Q in G for which TrFqe |Fq (f (Q)) = a. Suppose that
all sequences in Ψf (r, G) have period dividing k(N, r)/d. Then d is a divisor of
gcd(N − k(N, r), Tf (a), N n − 1) for all a ∈ Fq \{TrFqe |Fq (f (O))}.
Proof: All non-zero sequences in Ψf (r, G) have as period a divisor of k(N, r)/d.
Hence the number of times a occurs in the corresponding sequences is divisible by
d. Write b = TrFqe |Fq (f (O)). Then d divides N n Tf (a) with a ∈ Fq \ {b}, and d
divides N n Tf (b) − k(N, r). Since k(N, r) divides N nP − 1, d divides gcd(N n Tf (b) −
n
k(N, r), Tf (a), N − 1) for all a ∈ Fq \ {b}. Using a∈Fq Tf (a) = N , for all a ∈
Fq \{TrFqe |Fq (f (O))} it is found (after eliminating Tf (b)) that d divides
gcd(N n+1 − k(N, r), Tf (a), N n − 1).

The result follows directly from this. u
t
Example 5.6.4 Let E be the elliptic curve defined over F2 given by the equation
Y 2 + Y = X 3 + X + 1.
Let G be a prime-order subgroup of E(Fq ) with q an odd power of 2. Using the
addition formulas on E, one can derive that for this curve Tx (0) − 1 = Tx (1) = (N −
1)/2. Hence, according to the above theorem, d divides gcd((N − 1)/2, k(N, r) − 1).
Take for example r(X) = X 2 − X − 1, the Fibonacci-recursion. The polynomial
r(X) is irreducible if and only if N ≡ 2, 3 (mod 5). Assuming this, k(N, r) divides
2N + 2, since for any root ρ of r(X) the relation ρ2N +2 = (ρ · ρN )2 = (−1)2 = 1
holds. Here the fact was used that r(X) is absolutely irreducible and hence that its
roots are given by ρ and ρN . If furthermore the assumption k(N, r) = 2N + 2 is
made, d divides 3. So the period of the resulting binary sequence is either the full
period of the sequence of points on the elliptic curve, or a third of that.
5.7 Conclusion
Sequences obtained by using elliptic curves, as described in this section, certainly

appear to be pseudorandom. When one generates such sequences in practice, all
important statistical properties are well within the ranges one would expect a ran-
dom sequence to have (they pass the FIPS 140-1 statistical tests for randomness).
However, only a few statistical properties are proven to hold. The balance and au-
tocorrelation of these sequences are within the range that would be expected for a
random sequence. The question of whether or not these sequences satisfy the expec-
tation of other statistical tests (such as the next-bit test), remains open. Especially
in the area of using linear recurrencies on elliptic curves, more research is needed to
determine the cryptographic strength of sequences generated in this way.
References
[AW92a] M. Alabbadi and S. B. Wicker, Cryptoanalysis of the Harn and Wang

modification of the Xinmei digital signature scheme, Electronic Letters
28 (1992), no. 18, 1756–1758.
[AW92b] M. Alabbadi and S. B. Wicker, Security of Xinmei digital signature
scheme, Electronic Letters 28 (1992), no. 9, 890–891.
[AW93] M. Alabbadi and S. B. Wicker, Digital signature scheme based on error–
correcting codes, Proceedings of 1993 IEEE International Symposium on
Information Theory, 1993, p. 199.
[AW94] M. Alabbadi and S. B. Wicker, Susceptibility of digital signature schemes
based on error-correcting codes to universal forgery, Error control, cryp-
tology, and speech compression (Moscow, 1993), Springer, Berlin, 1994,
pp. 6–12.
[AW95] M. Alabbadi and S. B. Wicker, A digital signature scheme based on linear
error-correcting block codes, Advances in cryptology—ASIACRYPT ’94
(Wollongong, 1994), Springer, Berlin, 1995, pp. 238–248.
[Bar97] A. Barg, A large family of sequences with low periodic correlation, Dis-
crete Math. 176 (1997), no. 1-3, 21–27.
[BD02] P. H. T. Beelen and J. M. Doumen, Pseudorandom sequences from elliptic
curves, Finite Fields with Applications to Coding Theory, Cryptography
and Related Areas, Springer Verlag, 2002, pp. 37–52.
[BD03] P. H. T. Beelen and J. M. Doumen, Two Mersenne-like families of prime
numbers, Manuscript, 2003.
[BDL97] D. Boneh, R. A. DeMillo, and R. J. Lipton, On the importance of
checking cryptographic protocols for faults (extended abstract), Advances
in cryptology—EUROCRYPT ’97 (Konstanz), Springer, Berlin, 1997,
pp. 37–51.
[Bee01] P. H. T. Beelen, Algebraic geometry and coding theory, Ph.D. thesis, Eind-
hoven University of Technology, 2001.
[Ber97] T. A. Berson, Failure of the McEliece public-key cryptosystem under
message–resend and related–message attack, Advances in Cryptology –
67
68 REFERENCES
CRYPTO ’97, Lecture Notes in Computer Science 1294 (B. S. Kaliski Jr.,
ed.), Springer-Verlag, 1997, pp. 213–220.
[BKT99] A. Barg, E. Krouk, and H. C. A. v. Tilborg, On the complexity of mini-
mum distance decoding of long linear codes, IEEE Trans. Inform. Theory
45 (1999), no. 5, 1392–1405.
[Ble98] D. Bleichenbacher, Chosen ciphertext attacks against protocols based
on the RSA encryption standard PKCS #1, Advances in Cryptology -
CRYPTO 1998, Springer-Verlag, 1998, pp. 1–12.
[BMT78] E. R. Berlekamp, R. J. McEliece, and H. C. A. v. Tilborg, On the inherent
intractability of certain coding problems, IEEE Trans. Information Theory
IT-24 (1978), no. 3, 384–386.
[Bom66] E. Bombieri, On exponential sums in finite fields, Amer. J. Math. 88
(1966), 71–105.
[Bre89] D. Bressoud, Factorization and primality testing, Springer-Verlag, New
York, 1989.
[BS93] E. Biham and A. Shamir, Differential cryptanalysis of the data encryption
standard, Springer-Verlag, New York, 1993.
[BS96] E. Bach and J. Shallit, Algorithmic number theory. Vol. 1, MIT Press,
Cambridge, MA, 1996, Efficient algorithms.
[BS97] E. Biham and A. Shamir, Differential fault analysis of secret key cryp-
tosystems, Lecture Notes in Computer Science 1294 (1997), 513–522.
[CFS01] N. Courtois, M. Finiasz, and N. Sendrier, How to achieve a McEliece-
based digital signature scheme, Advances in Cryptology - ASIACRYPT
2001, Springer-Verlag, 2001, pp. 157–174.
[Cha95] F. Chabaud, On the security of some cryptosystems based on error-
correcting codes, Advances in cryptology—EUROCRYPT ’94 (Perugia),
Springer, Berlin, 1995, pp. 131–139.
[Cox89] D. Cox, Primes of the form x2 + ny 2 , John Wiley & Sons Inc., New York,
1989, Fermat, class field theory and complex multiplication.
[CS98] A. Canteaut and N. Sendrier, Cryptanalysis of the original McEliece cryp-
tosystem, Advances in cryptology—ASIACRYPT’98 (Beijing), Springer,
Berlin, 1998, pp. 187–199.
[DH82] W. Diffie and M. E. Hellman, New directions in cryptography, Secure
communications and asymmetric cryptosystems, Westview, Boulder, CO,
1982, pp. 143–180.
[DR98] J. Daemen and V. Rijmen, Aes proposal: Rijndael, 1998,
www.esat.kuleuven.ac.be/˜rijmen/rijndael/.
[Dum96] I. Dumer, Suboptimal decoding of linear codes: partition technique, IEEE
Trans. Inform. Theory 42 (1996), no. 6, part 1, 1971–1986, Codes and
complexity.
REFERENCES 69
[ElG85] T. ElGamal, A public key cryptosystem and a signature scheme based on

discrete logarithms, Advances in cryptology (Santa Barbara, Calif., 1984),
Springer, Berlin, 1985, pp. 10–18.
[FO99] E. Fujisaki and T. Okamoto, How to enhance the security of public-key
encryption at minimum cost, Public Key Cryptography, 1999, pp. 53–68.
[GBS00] G. Gong, T. Berson, and D. Stinson, Elliptic curve pseudorandom se-
quence generators, Selected areas in cryptography (Kingston, ON, 1999)
(Berlin), Springer, 2000, pp. 34–48.
[GL02] G. Gong and C. C. Y. Lam, Recursive sequences over elliptic curves,
Sequences and their Applications - SETA ’01, Springer, London, 2002,
pp. 182–196.
[GMT82] S. Goldwasser, S. Micali, and P. Tong, Why and how to establish a private
code on a public network, 23rd annual symposium on foundations of com-
puter science (Chicago, Ill., 1982), IEEE, New York, 1982, pp. 134–144.
[Gra01] J. Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), no. 234,
873–891.
[Hal94] S. Hallgren, Linear congruential generators over elliptic curves, Tech.
Report CS-94-143, Dept. of Comp. Sc., Carnegie Mellon Univ., 1994.
[Ham50] R. W. Hamming, Error detecting and error correcting codes, Bell System
Technical Journal 29 (1950), 147–160.
[HGS99] C. Hall, I. Goldberg, and B. Schneier, Reaction attacks against several
public-key cryptosystems, Proceedings of Information and Communica-
tion Security, ICICS’99, Springer-Verlag, 1999, pp. 2–12.
[HW79] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers,
fifth ed., The Clarendon Press Oxford University Press, New York, 1979.
[HW92] L. Harn and D. C. Wang, Cryptoanalysis and modification of digital signa-
ture scheme based on error–correcting codes, Electronic Letters 28 (1992),
no. 2, 157–159.
[Kah67] D. Kahn, The codebreakers: the story of secret writing, MacMillan Pub-
lishing Company, New York, NY, USA, 1967.
[KFL85] T. Kasami, T. Fujiwara, and S. Lin, An approximation to the weight dis-
tribution of binary linear codes, IEEE Trans. Inform. Theory 31 (1985),
no. 6, 769–780.
[KJJ99] P. Kocher, J. Jaffe, and B. Jun, Differential power analysis, Advances in
Cryptology - CRYPTO 1999, Springer-Verlag, 1999, pp. 388–397.
[KKS97] G. Kabatianskii, E. Krouk, and B. Smeets, A digital signature scheme
based on random error-correcting codes, Cryptography and coding
(Cirencester, 1997), Springer, Berlin, 1997, pp. 161–167.
70 REFERENCES
[KL95] I. Krasikov and S. Litsyn, On the accuracy of the binomial approximation

to the distance distribution of codes, IEEE Trans. Inform. Theory 41
(1995), no. 5, 1472–1474.
[Kob01] N. Koblitz, Almost primality of group orders of elliptic curves defined
over small finite fields, Experiment. Math. 10 (2001), no. 4, 553–558.
[Koc96] P. C. Kocher, Timing attacks on implementations of Diffie-Hellman,
RSA, DSS, and other systems, Lecture Notes in Computer Science 1109
(1996), 104–113.
[KS00] D. R. Kohel and I. E. Shparlinski, On exponential sums and group gen-
erators for elliptic curves over finite fields, Algorithmic number theory
(Leiden, 2000), Springer, Berlin, 2000, pp. 395–404.
[LMQ75] J. Leitzel, M. Madan, and C. Queen, Algebraic function fields with small
class number, J. Number Theory 7 (1975), 11–27.
[Mat93] M. Matsui, Linear cryptanalysis method for the DES cipher, Advances
in Cryptology: EUROCRYPT ’93, Proceedings, Lofthus, Norway, May,
1993, Lecture Notes in Computer Science 765 (Berlin, Heidelberg, New
York) (T. Helleseth, ed.), Springer Verlag, 1993, pp. 386–397.
[McE78] R. J. McEliece, A public–key cryptosystem based on algebraic coding the-
ory, DSN Progress Report 42–44, Jet Propulsion Laboratory, Pasadena,
1978, pp. 114–116.
[MOV97] A. J. Menezes, P. C. v. Oorschot, and S. A. Vanstone, Handbook of applied
cryptography, CRC Press, Boca Raton, FL, 1997, With a foreword by
Ronald L. Rivest.
[MS77] F. MacWilliams and N. Sloane, The theory of error-correcting codes. I,
North-Holland Publishing Co., Amsterdam, 1977, North-Holland Math-
ematical Library, Vol. 16.
[MS02] E. E. Mahassni and I. Shparlinski, The uniformity of distribution of con-
gruential generators over elliptic curves, Sequences and their Applications
- SETA ’01, Springer, London, 2002, pp. 257–264.
[Oak00] M. Oakes, Private communication, 2000.
[Per91] M. Perret, Multiplicative character sums and nonlinear geometric codes,
Eurocode ’90 (Udine, 1990), Springer, Berlin, 1991, pp. 158–165.
[Rib96] P. Ribenboim, The new book of prime number records, Springer-Verlag,
New York, 1996.
[RN89] T. R. N. Rao and K.-H. Nam, Private-key algebraic-code encryptions,
IEEE Trans. Inform. Theory 35 (1989), no. 4, 829–833.
[RSA78] R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital
signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2,
120–126.
REFERENCES 71
[Sha48] C. E. Shannon, A mathematical theory of communication, Bell System

Technical Journal 27 (1948), 379–423 and 623–656.
[Shp99] I. E. Shparlinski, Finite fields: theory and computation, Kluwer Academic
Publishers, Dordrecht, 1999, The meeting point of number theory, com-
puter science, coding theory and cryptography.
[Sil86] J. H. Silverman, The arithmetic of elliptic curves, Springer-Verlag, Berlin,
1986.
[Ste93] J. Stern, A new identification scheme based on syndrome decoding, Ad-
vances in Cryptology—CRYPTO ’93 (D. R. Stinson, ed.), Lecture Notes
in Computer Science, vol. 773, Springer-Verlag, 1993, pp. 13–21.
[Sti93] H. Stichtenoth, Algebraic function fields and codes, Springer-Verlag,
Berlin, 1993.
[Til92] J. v. Tilburg, Cryptanalysis of Xinmei digital signature scheme, Elec-
tronic Letters 28 (1992), no. 20, 1935–1936.
[Til93a] H. C. A. v. Tilborg, Error–correcting codes – a first course, Chartwell
Bratt Ltd, 1993.
[Til93b] J. v. Tilburg, Cryptanalysis of the Alabbadi–Wicker digital signature
scheme, Proceedings of Fourteenth Symposium on Information Theory
in the Benelux, 1993, pp. 114–119.
[Til94] J. v. Tilburg, Security-analysis of a class of cryptosystems based on lin-
ear error-correcting codes, Technische Universiteit Eindhoven, Eindhoven,
1994, Dissertation, Technische Universiteit Eindhoven, Eindhoven, 1994.
[VDT02] E. Verheul, J. M. Doumen, and H. C. A. v. Tilborg, Sloppy Alice attacks!
Adaptive chosen ciphertext attacks on the McEliece cryptosystem, Infor-
mation, Coding and Mathematics, Kluwer Academic Publishers, Boston
etc., 2002, pp. 99–119.
[Vos93] C. Voss, Abschätzungen der Parameter von Spurcodes mit Hilfe algebra-
ischer Funktionenkörper, Ph.D. thesis, Universität Essen, 1993.
[VW00] J. F. Voloch and J. L. Walker, Euclidean weights of codes from elliptic
curves over rings, Trans. Amer. Math. Soc. 352 (2000), no. 11, 5063–5076
(electronic).
[Wae40] B. L. v. d. Waerden, Moderne Algebra, J. Springer, Berlin, 1940.
[Wag83] S. S. Wagstaff, Jr., Divisors of Mersenne numbers, Math. Comp. 40
(1983), no. 161, 385–397.
[Wan90] X. M. Wang, Digital signature scheme based on error–correcting codes,
Electronics Letters 26 (1990), no. 13, 898–899.
[XD99] S. Xu and J. M. Doumen, An attack against the Alabbadi–Wicker scheme,
The 20th symposium on information theory in the Benelux, 1999.
72 REFERENCES
[XDT03] S. Xu, J. M. Doumen, and H. C. A. v. Tilborg, On the security of digital

signature schemes based on error–correcting codes, Designs, Codes and
Cryptography 28 (2003), no. 2, 187–199.
[YC03] S. Yates and C. Caldwell, The largest known primes, 2003, http://www.
utm.edu/research/primes/ftp/all.txt.
Index
Alabbadi–Wicker scheme, 26 Hamming weight, 2

Alice, 2 hash function, 1
alphabet, 2
analogous matrices, 25 Key Equation, 4
approximately binomial, 13
authentication, 1 Maximal Error Property, 6
autocorrelation, 52 Mersenne numbers, 38
message recovery scheme, 21
balance, 51 minimum distance, 3
binary entropy function, 13
non-repudiation, 1
Bob, 2
one-way function, 1
code, 2
codeword, 2 parity check matrix, 2
confidentiality, 1 Pocklington’s primality test, 38
crosscorrelation, 53 primality tests, 37
cryptosystem, 2 prime-generating elliptic curve, 39
Proth’s primality test, 37
data integrity, 1
digital signature scheme, 2 Rao–Nam cryptosystem, 24
dual code, 2 redundancy, 2
Eisenstein-Mersenne numbers, 43 side-channel attacks, 9
elliptic curve, 49 singular point, 50
encryption scheme, 2
error vector, 2 testing for primality, 37
error–correcting capability, 3 trace map, 51
Eve, 2 trapdoor one-way function, 1
Frobenius eigenvalue, 39 valuation, 50

function field, 50
Wagstaff conjecture, 45
Gauss-Mersenne numbers, 43 Weierstrass equation, 50
generator matrix, 2 weight distribution, 3
Goppa code, 3 weighted degree, 56
Hamming distance, 3 Xinmei scheme, 23
73
74 INDEX
Acknowledgements
First of all I would like to thank my utilization committee, under the adept leader-
ship of Henk van Tilborg, for the guidance they have given to my research. Consid-
ering the comparison of the original planning for my four years to the subjects dis-
cussed here, I am grateful for the freedom they granted me in choosing my favourite
subjects.
My thanks go out as well to Henk van Tilborg, Arjen Lenstra and Berry Schoen-
makers for suffering through the iterations of the thesis in front of you. Their
remarks, both mathematical and linguistic, have improved my thesis considerably.
Also, many thanks to the innumerable Ph.D. students who preceded me and who
continually refined the used LATEX style, to which I now made my own contribution.
Furthermore I want to thank many other people with whom I had many inter-
esting mathematical discussions. To name but a few, I am thinking of Peter Beelen,
Aart Blokhuis, Andries Brouwer, Jan Draisma, Ralf Gramlich, O.P. Lossers, Sander
van Rijnswou, Berry Schoenmakers, Martijn Stam and all the other people I will
mention here only implicitly.
Finally I would like to thank the technology foundation STW for funding my
Ph.D. position in the project Strong Authentication Methods, number EWI.4536.
75
76 Acknowledgements
Samenvatting
In dit proefschrift worden een aantal toepassingen van coderingstheorie binnen de

cryptografie behandeld. Het klassieke voorbeeld hiervan is het McEliece cryptosys-
teem, waarin een willekeurige lineaire code wordt gebruikt om berichten te kun-
nen versleutelen. De veiligheid van dit systeem is gebaseerd op één van de funda-
mentele problemen uit de coderingstheorie, namelijk het feit dat het decoderen in
een willekeurige code een NP-compleet probleem is.
Alhoewel de veiligheid van dit cryptosysteem nog fier overeind staat, moet (zoals
altijd) de implementatie van het cryptosysteem zorgvuldig gebeuren. Mocht een
aanvaller de mogelijkheid hebben om (herhaaldelijk) informatie te krijgen over het
al dan niet juist gevormd zijn van een cijfertekst, dan is het mogelijk om de versleu-
teling van een willekeurige cijfertekst ongedaan te maken, zoals in dit proefschrift is
aangetoond. In de praktijk kan het eenvoudig zijn om zulke informatie te vergaren:
de aanvaller zou bijvoorbeeld (op wat voor manier dan ook) toegang kunnen hebben
tot de foutmeldingen die het ontcijfer-apparaat van de ontvanger produceert, of het
zou kunnen zijn dat dit apparaat geautomatiseerd is en standaard een foutmelding
terug stuurt als de ontvangen cijfertekst niet kan worden ontcijferd. Voor het geval
dat het niet kan worden uitgesloten dat een aanvaller deze informatie bemachtigt,
worden een aantal suggesties gedaan om de besproken aanval tegen te gaan.
Een andere belangrijke toepassing van cryptografie zijn zogenaamde digitale
handtekeningen. Het doel hiervan is het digitale equivalent van een schriftelijke
handtekening onder een papieren document. In 1990 werd door Wang een sys-
teem voorgesteld dat gebaseerd is op coderingstheorie. Daarna werd dit systeem in
relatief korte tijd verscheidene malen gebroken en weer gerepareerd. In dit proef-
schrift wordt een korte historie hiervan gegeven. Tevens wordt er aangetoond dat
in de laatste incarnatie van deze familie handtekeningenschema’s een vervalsing van
een handtekening mogelijk is, als men alleen de publieke sleutel kent. Tevens wordt
nogmaals beargumenteerd dat een dergelijke opzet voor een handtekeningenschema
tot falen gedoemd is.
Een ander aspect van cryptografie is het genereren van pseudorandom rijen.
Deze worden niet alleen in vele cryptografische protocollen direct gebruikt, maar
ook heeft elk cryptosysteem een geheime sleutel nodig. De praktijk leert dat het
niet verstandig is om die sleutel door mensen te laten kiezen (als het cryptosysteem
dat al toelaat), maar dat het beter is om deze willekeurig te nemen. Helaas is
het genereren van willekeurige getallen relatief duur. Edoch is een iets zwakkere
77
78 Samenvatting
eis voldoende, namelijk dat deze getallen random lijken te zijn. In dit proefschrift
wordt een methode beschreven om pseudorandom rijen te genereren met behulp van
recurrente betrekkingen op elliptische krommen. Tevens wordt een aanzet gedaan
tot het bewijzen van de cryptografische sterkte van deze generator.
In cryptografie worden vaak priemgetallen gebruikt. Onder andere hebben ze
een directe toepassing in het RSA cryptosysteem. Deze praktische toepassing van
priemgetallen heeft het fundamentele onderzoek ernaar zeker gestimuleerd. In dit
proefschrift wordt daaraan een steentje bijgedragen met de introductie van twee
nieuwe families getallen, waarvan de primaliteit efficiënt getest kan worden. Beide
families vertonen grote verwantschap met de Mersenne getallen. Onder andere is
in dit proefschrift het Wagstaff-vermoeden gegeneraliseerd naar de distributie van
priemgetallen in de twee nieuwe families.
Curriculum Vitae
Jeroen Doumen werd geboren op 1 juli 1975 te Warstein, Duitsland. Na te zijn

teruggekeerd naar Nederland, behaalde hij aldaar bij het Katholiek Gymnasium
Rolduc te Kerkrade in 1993 het gymnasium diploma. Daarna verhuisde hij naar Lei-
den om aan de Leidse universiteit wis– en natuurkunde te gaan studeren. Beide stu-
dies werden met succes afgerond: hij studeerde eind 1998 af bij prof.dr. J.M.J. van
Leeuwen in de theoretische natuurkunde met de scriptie Criticality in the Trans-
”
verse Ising Model“, en in de wiskunde studeerde hij begin 1999 bij drs. M.A.J.G.
van der Vlugt af met de scriptie Gewichten van deelcodes en krommen met veel
”
punten“.
Eind 1998 begon hij aan de Technische Universiteit Eindhoven als AIO bij
prof.dr.ir. H.C.A. van Tilborg aan het STW-projekt EWI.4536, getiteld Strong
”
Authentication Methods“. Het resultaat van deze arbeid ligt voor U.
79
80 Curriculum Vitae

CR 2

Uploaded by

Copyright:

Available Formats

CR 2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CR 2

Uploaded by

Copyright:

Available Formats

Some Applications of Coding

CIP-DATA LIBRARY TECHNISCHE UNIVERSITEIT EINDHOVEN

Some applications of coding theory in cryptography / by Jeroen M.

Printed by Eindhoven University Press.

ter verkrijging van de graad van doctor aan de

Jeroen Mathias Doumen

geboren te Warstein, Duitsland.

prof.dr.ir. H.C.A. van Tilborg

1 Preliminaries and notation 1

2 Adaptive chosen ciphertext attacks on the McEliece cryptosystem 9

3 Digital signature schemes based on error–correcting codes 21

4 Two families of Mersenne–like primes 37

4.3 Prime-generating elliptic curves . . . . . . . . . . . . . . . . . . . . . 39

5 Pseudorandom sequences from elliptic curves 49

Preliminaries and notation

The aim of cryptography is to provide secure transmission of messages, in the

1.2 Coding Theory

The (Hamming) distance dH (x, y) between vectors x and y is defined as the

1.2.1 Goppa codes

the parity check matrix of CΓ is given by

G(γ1 )−1 G(γn )−1

The syndrome polynomial Sy (x) is zero if and only if y ∈ CΓ . Now write y as

y = c + e, where c ∈ CΓ and wH (e) ≤ t. (1.2)

One way to do this is by using Euclid’s extended algorithm. On input of two

S(x)σ(x) ≡ σ 0 (x) (mod G(x)).

β 2 (x) (xS(x) + 1) ≡ S(x)α2 (x) (mod G(x)).

map y 7→ y 2 is an automorphism, and thus is it possible and well-defined to take

R(x)β(x) ≡ α(x) (mod G(x)).

On this form, Euclid’s extended algorithm can be applied as described earlier.

1.2.2 The Maximal Error Property

Property 1.2.2 (Maximal Error Property ) On input of a vector y ∈ Fnq , the

Proposition 1.2.3 Let C be a Goppa code with designed error–correcting capability

Proof: First, suppose the characteristic of Fq is not equal to 2, suppose that

ωy (γi )/σy (γi ) if i ∈ E 0 ,

Adaptive chosen ciphertext attacks

Summary. Attacks are introduced in which a malicious sender or an adaptive

2.2 The McEliece Public–Key Cryptosystem

r = mG0 + e (= mSGP + e). (2.1)

As eP −1 has the same weight as e, Bob can determine mS (and eP −1 ) from

Assumption 2.2.1 (The security of McEliece cryptosystem) The following ob-

Sec–1. k ≈ n/2 ≥ 512: this makes “syndrome decoding” as well as an exhaustive

2.3 An adaptive chosen ciphertext attack

Now the attack on the McEliece cryptosystem will be described.

Algorithm 2.3.1 [Adaptive chosen ciphertext attack on McEliece]

Step 1. Increase the number of errors made by Alice to exactly t.

Before analyzing this algorithm, we introduce the following notion.

iii) If the weight distribution of C is approximately binomial, then

d(e + f , e + f 0 ) = d(f , f 0 ) = w(f − f 0 ) ≤ w(f ) + w(f 0 ) ≤ 2t < d.

As e + f and e + f 0 are two distinct members of C at distance less than d, we

Let c be a codeword in C of weight 2t + 1. Then each (t + 1)–subset of the

iii) By assumption the relation

holds. It follows from ii) that

for each 0 ≤ m ≤ n. This can be rewritten as

Note that since

it also follows that

Proof of Theorem 2.3.3: Consider any r = c + e where c ∈ C and w(e) = s ≤ t.

Countermeasures to the adaptive chosen ciphertext attack on the McEliece cryp-

• if both probes give an error–message, then ei = 0,

• if only one probe gives an error–message, then ei 6= 0 and ei is in fact deter-