A Course in Mathematical Cryptography

Gilbert Baumslag, Benjamin Fine, Martin Kreuzer, Gerhard Rosenberger

• Publisher: De Gruyter
• Year: 2015
• ISBN:
  9783110386165
• Edition: 1
• Topic: Informatik
• Subtopic: Informatik Allgemein

Cryptography has become essential as bank transactions, credit card infor-mation, contracts, and sensitive medical information are sent through inse-cure channels. 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 and covers a wide range of topics in mathematical cryptography. It is primarily geared towards graduate students and advanced undergraduates in mathematics and computer science, but may also be of interest to researchers in the area.

Besides the classical methods of symmetric and private key encryption, the book treats the mathematics of cryptographic protocols and several unique topics such as

• Group-Based Cryptography
• Gröbner Basis Methods in Cryptography
• Lattice-Based Cryptography

1 Basic Ideas of Cryptography

1.1 Mathematical Cryptography

The subject of this book is mathematical cryptography. By this we mean the mathematics involved in cryptographic protocols. We will define, and make precise, all these terms as we proceed. As the field has expanded, using both commutative and non-commutative algebraic objects as cryptographic platforms, we felt that a book describing and explaining all these mathematical methods would be of considerable value.

Cryptography or cryptology is loosely the science of encrypting and decrypting secret codes, and the related task of breaking or uncovering secret codes. The science of cryptography touches on many other disciplines, both within mathematics and computer science and in engineering. In mathematics, cryptology uses, and touches on, algebra, number theory, graph and lattice theory, algebraic geometry and probability and statistics. Analysis of cryptographic security leads to using theoretical computer science especially complexity theory. The actual implementation of cryptosystems, and the hard work of carrying out security analysis for specific cryptosystems falls into engineering and practical computer science and computing. In this book we will look primarily at the first part, the mathematics of cryptographic protocols. We will not look at all at hardware implementation. In Section 1.2 we will present many of the terms and mathematical formulations in cryptology. Section 1.2 will be further expanded in Chapter 2.

Up until fairly recently, cryptography was mainly concerned with message confidentiality - that is sending secret messages so that interceptors or eavesdroppers cannot decipher them. The discipline was primarily used in military and espionage situations and as recently as the 1956 Encyclopedia Brittanica article on Cryptography said that there seemed to be only limited use in business and commerce. Two things changed all that. The first was the increased capability and use of computers and computing. This both allowed more complex encryption systems that could not be done by hand but could be on a computer, and required more complex encryption, since cryptanalysis, that is, code breaking, was enhanced by the computer. The second thing that skyrocketed the use of cryptographic methods was the discovery of workable one way functions that then allowed for public key cryptosystems. This allowed the transmission of sensitive data over public airwaves even though any potential attacker could view this data and further the attacker knew the encryption technique. In Section 1.3 we give a very brief history of cryptography while in Section 1.5 and then again in Chapter 2 we describe the basic ideas differentiating classical or symmetric key cryptography from public key cryptography.

An important aspect of cryptographic protocols are their security, that is the ability of the encryption to withstand attacks from unwanted adversaries. Since modern cryptography is done on a computer, cryptographic security must bring in ideas from computer science and complexity theory. We will present some of these ideas from a mathematical viewpoint in Chapter 3. The book [MSU1] by Myasnikov, Shpilrain and Ushakov provides a much more extensive discussion of complexity theory and its relationship and use relative to cryptography.

Traditionally, the main mathematical tools involved in cryptographic protocols were number theoretic. To encrypt an alphabet with N letters the letters were considered as modular integers 0,1, 2,N - 1 in the modular ring

_N. Number theoretic functions on

_N were then used. The main public key cryptographic methods, Diffie- Hellman and RSA, are based on supposedly hard number theoretic problems, the discrete logarithm problem and the factorization problem respectively. We touch on these ideas in Section 1.4 and then much more fully in Chapter 6. We will discuss the main traditional public key methods in Chapter 7. In an attempt to build cryptosystems with smaller necessary key spaces, algebraic geometry was introduced to cryptography. The concepts of elliptic curves and their corresponding elliptic curve groups were combined with the Diffie-Hellman concepts to build elliptic curve cryptography. We discuss elliptic curve methods in Chapter 8.

The traditional cryptographic methods, both symmetric key and public key, such as the RSA algorithm, Diffie-Hellman, and elliptic curve methods, are number theory based. Hence, from a theoretical point of view, they depend on the structure of abelian groups. Although there have been no successful attacks on the standard protocols, there is a feeling that the strength of computing machinery has made these techniques less secure. The big cloud in this direction are quantum algorithms and the possibility that a workable quantum computer can be built. Quantum algorithms can break the present versions of both Diffie-Hellman and RSA. We will briefly touch on quantum algorithms in Chapter 3.

As a result of this, there has been an active line of research to develop and analyze new cryptosystems and key exchange protocols based on non-commutative cryptographic platforms. This line of investigation has been given the broad title of noncommutative algebraic cryptography.

Up to this point the main sources for non-commutative cryptographic platforms have been non-abelian groups. In cryptosystems based on these objects, algebraic properties of the platforms are used prominently in both devising cryptosystems and in cryptanalysis. In particular the difficulty, in a complexity sense, of certain algorithmic problems in finitely presented groups, such as the conjugator search problem, has been crucial in encryption and decryption. We give an introduction to these group theoretic ideas in Chapters 9 and 10. Chapter 11 deals with the main public key methods using non-abelian groups, the Ko-Lee method and the Anshel-Anshel-Goldfeld method.

The main sources for non-abelian groups are combinatorial group theory and linear group theory. Braid group cryptography, where encryption is done within the classical braid groups, is one prominent example. The one-way functions in braid group systems are based on the difficulty of solving group theoretic decision problems such as the conjugacy problem and conjugator search problem. Although braid group cryptography had initia...