×

Elliptic curves in cryptography. (English) Zbl 0937.94008

London Mathematical Society Lecture Note Series. 265. Cambridge: Cambridge University Press. xv, 204 p. (1999).
This book is a very well written description of the use of elliptic curves in public key cryptography. It could be read by students/researchers in cryptography, mathematics or by engineers. The book contains ten chapters and an appendix.
The security of public key schemes is based on the difficulty of solving mathematical problems. Whereas the integer factorization problem (IFP) gave birth in the 70s to RSA, the discrete logarithm problem produced cryptography based on finite groups. The first chapter of the book under review introduces these concepts, especially: the Diffie-Hellman key exchange, the ElGamal encryption, the ElGamal digital signature scheme, the digital signature algorithm, and the Nyberg-Rueppel digital signature scheme. The advantage of formulating the discrete logarithm problem for elliptic curves defined over finite fields (ECDLP) is provided by the fact that, to date, no algorithm is known which breaks the ECDLP in sub-exponential time, whereas there exist algorithms which can factorize integers in sub-exponential time. As a consequence, to date, elliptic curves defined over finite fields provide with small parameters the same amount of security as e.g. RSA with bigger parameters. Hence elliptic curves are particularly useful in the context of chip cards.
Chapter two is devoted to the implementation of the underlying field arithmetic, both in the case of odd and even characteristic. In the case of odd characteristic, the underlying field is simply \({\mathbb F}_p\), where \(p\) denotes a large prime (of length at least \(163\) bits say).
Chapter three is a very nice abstract of the theory of the arithmetic on elliptic curves, with special insight devoted to curves defined over finite fields, and the Weil pairing. Isogenies and modular polynomials are introduced as well.
Chapter four is more practical: it describes point addition, multiplication, compression and the Frobenius expansion.
Chapter five describes the state of the art regarding known attacks on ECDLP. As a consequence, the reader knows which situations to avoid in order to have a (hopefully) secure scheme based on elliptic curves.
An important step for elliptic curve cryptography is to determine the group order. Chapter six describes the main approaches.
The most used method for random curves is provided by Schoof’s algorithm, later refined by Atkin, Elkies, then by Couveignes, Morain, Müller, etc. as described in chapter seven.
The problem of computing the order of the group defined by an elliptic curve defined over a finite fields requires, as seen above, lots of stuff and computation time. A more practical way would be to reverse the problem: given a number \(n\), is it possible to construct an elliptic curve defined over a finite field whose group order equals \(n\), and which is useful in cryptography? The answer is (sometimes) yes, and provided by elliptic curves with complex multiplication, as described in chapter eight.
Elliptic curves may have other practical applications: finding small factors (say up to \(40\) bits) of integers, or proving that a given number is prime (ECPP). These applications are outlined in chapter nine.
The last chapter considers the generalization of systems based on elliptic curves to hyperelliptic curves.
An appendix contains explicit examples, and is very well detailed.
Apart from a preface, a guide for abbreviations and notations, and the content described above, the book contains of course a bibliography, but also an author and a very useful subject index. Many of the techniques described in this book are currently discussed in order to be standardized (IEEE-P1363 and ANSI X9.42, X9.62, X9.63 of the American Bankers Association). This shows how close to practical applications this book is.

MSC:

94A60 Cryptography
94-02 Research exposition (monographs, survey articles) pertaining to information and communication theory
14H52 Elliptic curves
11G05 Elliptic curves over global fields
PDFBibTeX XMLCite