Customer Reviews

Handbook of Elliptic and Hyperelliptic Curve Cryptography (Discrete Mathematics and Its Applications)

5 star:		(4)
4 star:		(0)
3 star:		(0)
2 star:		(0)
1 star:		(0)

 

 

Elliptic curve cryptography is now an entrenched field and has been subjected to an enormous amount of research in the last fifteen years. As soon as encryption schemes based on arithmetic in elliptic curves were proposed, it was natural to speculate on whether these schemes could be generalized to hyperelliptic curves or even general abelian varieties. This book gives an overview of what has been done, and even though most of the proofs are omitted, it does serve a need for those interested in the latest developments in the subject. This reviewer did not read the entire book, but concentrated instead on only a few parts that discussed developments in the last few years. Just skimming the book though will reveal that the authors have been very thorough in giving the reader the necessary mathematical background for a study of ECC and HECC cryptography. Readers needing more detailed background can consult the many references.

As expected, a substantial portion of the book is devoted to point counting methods. One of the methods discussed is the p-adic approach to counting the number of points on an elliptic curve over a field with a small characteristic, with the three most practical ones given the most attention. One of these, the Satoh algorithm, first computes the p-adic approximation of the canonical lift of an elliptic curve E over a finite field F(q), where q = p^d and p is a small prime. This involves lifting the j-invariants using a multivariate version of Newton's root finding algorithm. The trace of the Frobenius endomorphism must then be recovered, and this is done by using the action of the lift on a holomorphic differential on the lift. The resulting factoring problems are formidable, so instead the q-th Verschiebung, which is the dual isogeny to the Frobenius endomorphism is used. The Verschiebung is a separable morphism and the trace of an endomorphism is the trace of its dual. These facts are used to express the trace of the Frobenius endomorphism as a product (modulo q) of coefficients in Z(q). These coefficients are then calculated using certain polynomials.

Another algorithm using the p-adic approach to counting is the Arithmetic-Geometric-Mean (AGM) algorithm, which is discussed for the 2-adic case. As the name implies, this method is based on the AGM iteration, wherein a sequence of elliptic curves is constructed all of which are 2-isogenous to each other. This sequence is constructed so that it converges to the canonical lift of an ordinary elliptic curve, and then an explicit formula for the trace of the Frobenius map is derived. It is then shown how to extend the AGM algorithm to hyperelliptic curves by interpreting it as a special case of the Riemann duplication formula for theta functions.

The third p-adic algorithm discussed is called the Kedlaya algorithm and involves working with the affine curve associated to a hyperelliptic curve of genus g. Associated with this affine curve is its `dagger algebra,' the latter of which is discussed in the book and has its origins in the Monsky-Washnitzer cohomology for nonsingular affine curves over a finite field. This cohomology, which is currently listed under the classification of `rigid cohomology' is a cohomology for algebraic fields over fields of nonzero characteristic and can be considered to be a version of de Rham cohomology (in positive characteristic). In arises when one attempts to lift the Frobenius endomorphism on the coordinate ring of the curve to the coordinate ring of a lift of the curve. Taking the p-adic completion of the coordinate ring of the lift results in a de Rham cohomology which is even larger than the coordinate ring (the limit of exact differentials may not be exact), and so one works with a subring of the completion, which is called the `dagger ring.' The Frobenius endomorphism on the coordinate ring can then be lifted to a (Z(q)) endomorphism on the dagger ring. One can then define differentials of elements in the dagger ring, yielding a module over the dagger ring. The kernel and cokernel of this differential map can then be used to construct the zeroth and first Monsky-Washnitzer cohomology groups. The lift of the Frobenius endomorphism to the dagger ring induces an endomorphism on the cohomology groups, and this allows a Lefschetz fixed point formula to be proved, thus giving the number of rational points on the curve. The Kedlaya algorithm essentially follows this approach to do the point counting, but outputting the zeta function and working only for p greater than or equal to 3.

The book is not just a discussion on theoretical developments and computational algorithms, as an entire part of the book is devoted to applications. One of the applications discussed is that of `smart cards' which to date have been one of most widely used applications of cryptography. An entire chapter is spent on the hardware of smart cards, followed by one on how to attack the implementations of cryptosystems. One particular method for extracting the keys from inside a tamper-proof device involves the use of `power consumption analysis,' which is discussed in some detail in this chapter. The power consumption curve of the device or smart card is analyzed by the attacker, and this, coupled with an understanding of cryptographic algorithms, allows the keys to be compromised. Countermeasures against these attacks are discussed in the next chapter. The discussion is general enough in these chapters to give the motivated reader enough information to experiment with both attacking and with designing and testing effective countermeasures.

don't be fooled: This is a book written by experts, for professionals. The introductory chapters "cover" the mathematical preliminaries, but if you're not already familiar with the concepts, you won't get enough help there to be able to digest the real content of the book, which is very detailed, and looks to be very complete.

This is a reference book, not a textbook.

I gave it a 5-star rating because it would not be fair to down-grade the book because of my own limitations. However, in all honesty, I think most people interested in Elliptic Curve Cryptography will want to be introduced at "lower altitude".

When I first opened this book, a tear fell from my eye. Never in my life have I seen such mathematical beauty as summarized from this book. Elliptic curves, isogenies, complex multiplication, higher order abelian varieties, finite fields, point counting, Teichmuller modulus, p-adic numbers, and applications to cryptography: it's all there, and in one amazing book. And the algorithms are written so perfectly that it is easy to translate to the computer language of your choice. Ladies and gentlemen, I promise you, you will not be disappointed by this masterpiece.

It is one of the best books about elliptic curve cryptography, taking the reader from the basics of number theory to the elaborate and tricky field of elliptic curves.
It takes into discussion both theoretical and practical aspects of the domain.