erators for elliptic curves over ¬nite ¬elds, Algorithmic number theory

(Leiden, 2000), Springer, Berlin, 2000, pp. 395“404.

[LMQ75] J. Leitzel, M. Madan, and C. Queen, Algebraic function ¬elds 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 ¬elds: 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 identi¬cation 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 ¬elds 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 ¬rst 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, Absch¨tzungen der Parameter von Spurcodes mit Hilfe algebra-

a

ischer Funktionenk¨rper, Ph.D. thesis, Universit¨t Essen, 1993.

o a

[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. Wagsta¬, 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

Key Equation, 4

analogous matrices, 25

approximately binomial, 13

Maximal Error Property, 6

authentication, 1

Mersenne numbers, 38

autocorrelation, 52

message recovery scheme, 21

minimum distance, 3

balance, 51

binary entropy function, 13

non-repudiation, 1

Bob, 2

one-way function, 1

code, 2

codeword, 2 parity check matrix, 2

con¬dentiality, 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

testing for primality, 37

error vector, 2

trace map, 51

error“correcting capability, 3

trapdoor one-way function, 1

Eve, 2

valuation, 50

Frobenius eigenvalue, 39

function ¬eld, 50

Wagsta¬ conjecture, 45

Weierstrass equation, 50

Gauss-Mersenne numbers, 43

weight distribution, 3

generator matrix, 2

weighted degree, 56

Goppa code, 3

Xinmei scheme, 23

Hamming distance, 3

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 su¬ering 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 re¬ned the used L TEX style, to which I now made my own contribution.

A