Historically, secret codes and ciphers were placed in the realm of espionage and diplomacy. Although some people considered the mathematics of devising and breaking codes, it remained for a long time a discipline on the fringes of mathematics. Several things changed this view. First, sophisticated mathematical techniques were developed during the Second World War to aid in the cryptanalysis of the Enigma code and other war time ciphers. Then the widespread usage of computers and the advent of the internet led to the need of sending financial and other sensitive information over public channels. This sparked an intensive development of mathematical cryptography, both symmetric and public key.
Traditionally, cryptography refers to the science and/or art of devising and implementing secret codes and ciphers, while cryptanalysis is the science and/or art of breaking them. The whole disciple, cryptography plus cryptanalysis, is usually called cryptology. Sometimes however, cryptography is used in place of cryptology.
At present most people are familiar with the phrase “you are now entering an encrypted page...”. Cryptography has become essential as bank transactions, credit card information, contracts, and sensitive medical information are sent through insecure channels. Clearly, this must be done in encrypted form. This leads us to the concept of public key cryptography which deals with the problem of hiding secret data on open channels when every potential attacker knows the encryption method.
True public key methods were born with the rise of high speed computing and with the discovery by Diffie and Hellman in 1976 (actually known earlier to British Intelligence) of a true one-way function. The use of the computer was essential because arithmetic with very large numbers was necessary. A second public-key method, the RSA method, was developed by Rivest, Shamir, and Adleman a year later. These beginnings turned cryptography into a major discipline for both study and research in mathematics and in computer science. Today many, if not most, universities offer courses in cryptography. These courses are really of two different types. The first is geared to the mathematical aspects of the subject while the second deals with the computer science and engineering aspects, that is how to implement a mathematical cryptosystem or cryptanalysis on a computer or other physical devices.
This book is concerned with the mathematical, especially algebraic, aspects of cryptography. It grew out of many courses presented by the authors over the past twenty years at various universities: City University of New York for Gilbert Baumslag, Fairfield University, City University of New York, and the University of Dortmund for Ben Fine, University ofRegensburg, University of Dortmund, and University of Passau for Martin Kreuzer, and University of Dortmund, University of Passau, and the University of Hamburg for Gerhard Rosenberger. These courses covered a wide range of topics within cryptography and were presented at a variety of levels. The authors have had numerous Ph.D. and Masters level students in the discipline which has become an extremely popular area. In the following 15 chapters we cover a wide range of topics in mathematical cryptography. They are primarily geared towards graduate students and advanced undergraduates in mathematics and computer science, but may also be of interest to researchers in the area. We feel that this book could be a suitable text for first and second year Master level courses which may even include elliptic curve methods, group based techniques, as well as cryptography using Gröbner bases.
The book can be roughly divided into four parts. The first part, consisting of Chapters 1 to 4, covers the general ideas of cryptography and cryptanalysis. Starting from the most basic constructions, we define all the relevant material: cryptosystems, key spaces, as well as encryption and decryption maps. We also discuss the distinction between symmetric and asymmetric encryption and describe the basic outline of public key cryptography. Moreover, we introduce statistical cryptanalysis and point out some ideas from complexity theory. In Chapter 4 we present additional cryptographic protocols such as authentication, digital signatures and zero-knowledge proofs.
Part two, comprising Chapters 5 through 8, deals with number theoretic cryptographic methods. Chapters 5 and 6 introduce the fundamental ideas needed from number theory. Then, in Chapter 7, we apply these to develop common number theoretic public key cryptosystems and protocols: Diffie-Hellman, RSA, ElGamal, and Rabin. In Chapter 8 we provide a detailed explanation of elliptic curves and elliptic curve cryptography.
Chapters 9 to 12 form the third part which presents group-based cryptography. It deals with cryptosystems and crytographic protocols whose platforms are non-abelian groups. Combinatorial group theory plays the central role here, and we cover the necessary material on finitely presented groups in Chapter 9. In Chapter 10 we introduce free group cryptography and the Wagner-Magyarik method which was the seminal idea in the discipline. We also discuss in that chapter the use of matrix groups and a secure back-up password protocol that utilizes combinatorial group theory. In the first half of Chapter 11 we introduce the best-known public-key group based cryptosystems: the Ko-Lee protocol and the Anshel-Anshel-Goldfeld protocol. Braid groups were suggested as potential platforms for these protocols. So, the second half of Chapter 11 is concerned with the general theory of braid groups and braid-group cryptography. In Chapter 12 we collect some further suggestions for using finitely presented groups in a cryptographic setting.
The final part, consisting of Chapters 13,14, and 15 deals with Gröbner basis and lattice-based methods. Chapter 13 starts by introducing Gröbner bases of commutative polynomial ideals and Buchberger’s Algorithm to compute them. They are used both in commutative Gröbner basis cryptosystems and in some techniques of algebraic cryptanalysis explained in the second part of this chapter. In Chapter 14 we extend Gröbner bases to non-commutative polynomial rings and even two-sided free modules over these. Thereby quite general Gröbner basis cryptosystems can be constructed which include most of the methods presented in the earlier chapters. In the last chapter, Chapter 15, we give a short overview of lattices and lattice-based cryptography.
Special thanks are due to many of our students who, over the years, have looked at and made suggestions on the evolving versions of this book. We are especially grateful to Anja Moldenhauer for providing excellent and detailed help with both typesetting and editing parts of this book. Further, we cordially thank our wives and families whose massive amounts of patience and support were absolutely indispensable for the creation of a voluminous monograph such as this one.
While this book was being completed, tragically our colleague, co-author and friend, Gilbert Baumslag, died. Gilbert was one of the foremost researchers in the world in infinite group theory and developed many computational techniques for finitely presented groups. Over the past decade he had been active in transferring this knowledge to group-based cryptography. It is our hope that this book honors his memory and his contribution.
Fairfield, Passau, and Hamburg,
in January 2015,
Benjamin Fine,
Martin Kreuzer,
and Gerhard Rosenberger