A Course in Mathematical Cryptography

Book Preface

Historically, secret codes and cipherswere 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 SecondWorldWar to aid in the cryptanalysis of the Enigma code and otherwar 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 cryptographywhich 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 numberswas necessary.Asecond 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 of Regensburg, 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 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………………

Contents
Preface
1 Basic Ideas of Cryptography
2 Symmetric Key ~ Spam ~
3 Cryptanalysis and Complexity
4 Cryptographic Protocols
5 Elementary Number Theoretic Techniques
6 Some Number Theoretic Algorithms
7 Public Key Cryptography
8 Elliptic Curve Cryptography
9 Basic Concepts from Group Theory
10 Non-Commutative Group Based Cryptography
11 Platform Groups and Braid Group Cryptography
12 Further Applications Using Group Theory
13 Commutative Grobner Basis Methods
14 Non-Commutative Grobner Basis Methods
15 Lattice-Based Cryptography
Bibliography
Index