Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato (Q5906858)

This book is intended as a text for a course on cryptography, with an emphasis on algebraic methods. It is largely intended for graduate students in mathematics or computer science although it is not beyond the reach of advanced undergraduates. The first three chapters contain the background on cryptographic primitives, complexity and algebra, necessary to appreciate the last three chapters on three types of cryptographic systems: hidden monomial, combinatorial-algebraic and elliptic and hyperelliptic cryptosystems. The first chapter on cryptography reviews the idea of public key cryptosystems and includes interesting discussions on RSA, hash functions, digital signatures, Diffie-Hellman key exchange, secret sharing, coin flipping, bit commitment and cryptosystems in general. The following chapter contains an informal, yet surprisingly comprehensive and useful, discussion of the notions of complexity so necessary for an understanding of some of the fundamental results of cryptography. After some elementary results on number theory and algorithms, it considers the classes of decision problems P, NP and NP-complete, as well as the notion of problem reduction and randomized algorithms. Chapter 3 on Algebra contains the standard material on finite fields and the Euclidean algorithm for polynomials, before introducing topics such as the Hilbert basis theorem, the Hilbert nullstellensatz theorem and Gröbner bases. The final three chapters contain discussions of specific cryptosystems not well covered in other texts on the subject. Chapter 4 introduces the Imai-Matsumoto cryptosystem and the technique of Patarin in both breaking this system as well as proposing extensions and generalizations of it. The fifth chapter considers combinatorial-algebraic cryptosystems and the implications of a theorem of Brassard on such systems. The final chapter contains a review of the central problems associated with elliptic curve cryptosystems, including a discussion of the Jacobian of hyperelliptic curves, as a group for use in cryptography. An appendix on hyperelliptic curves from an algebraic-geometric perspective, written by Menezes, Wu and Zuccherato, is included. Answers to all problems in the text are also given. The book is a welcome addition to the literature of cryptography.