Mathematics, cryptology, and technology
Andrew Odlyzko
AT&T Labs - Research
The start of the 21st century is a golden age for applications of
mathematics in cryptology. The beginnings of this age can be traced
to the work of Rejewski, Rozycki, and Zygalski on breaking Enigma.
Their work was a breakthrough in several ways. It made a tremendous
practical contribution to the conduct of Word War II. At the same
time, it represented a major increase in the sophistication of the
mathematical tools that were used. Ever since, mathematics has been
playing an increasingly important role in cryptology. This has been
the outcome of the intricate relationships of mathematics, cryptology,
and technology, relationships that have been developing for a long
time.
While codes and ciphers go back thousands of years, systematic study
of them dates back only to the Renaissance. Such study was stimulated
by the rapid growth of written communications and the associated
postal systems, as well as by the political fragmentation in Europe.
In the 19th century, the electric telegraph provided an additional
spur to the development of cryptology. The biggest impetus, though,
appears to have come with the appearance of radio communication at the
beginning of the 20th century. This technological development led to
growth of military, diplomatic, and commercial traffic that was open
to non-intrusive interception by friend or foe alike. The need to
protect such traffic, from interception was obvious, and led to the
search for improved codes and ciphers. These, in turn, stimulated the
development of cryptanalytic methods, which then led to development of
better cryptosystems, in an endless cycle. What systems were built
has always depended on what was known about their security, and also
on the technology that was available.
Between the two world wars, the need for encrypting and decrypting
ever greater volumes of information reliably and securely, combined
with the available electromechanical technology, led many cryptosystem
designers towards rotor system. Yet, as Rejewski, Rozycki, and
Zygalski showed, the operations of rotor machines created enough
regularities to enable effective cryptanalysis through mathematical
techniques. This was yet another instance of what Eugene Wigner has
called the "unreasonable effectiveness of mathematics," in which
techniques developed for abstract purposes turn out to be surprisingly
well suited for real applications.
The sophistication of mathematical techniques in cryptography
continued increasing after World War II, when attention shifted to
cryptosystems based on shift register sequences. A quantum jump
occurred in the 1970s, with the invention of public key cryptography.
This invention was itself stimulated by technological developments,
primarily the growth in information processing and transmission. This
growth was leading to explosive increases in the volume of electronic
transactions, increases that show no signs of tapering off even today,
a quarter century later. The large and heterogeneous populations of
users that were foreseen in developing civilian settings were leading
to problems, such as key management and digital signatures, that
previously had not been as severe in smaller and more tightly
controlled military and diplomatic communications. At the same time,
developments in technology were offering unprecedented possibilities
for implementing complicated algorithms. Mathematics again turned out
to provide the tools that were used to meet the challenge.
The public key schemes that were invented in the 1970s used primarily
tools from classical number theory. Yet as time went on, the range of
applicable mathematics grew. Technology continued improving, but in
uneven ways. For example, while general computing power of a personal
computer grew explosively, there was also a proliferation of small,
especially wireless devices, which continued to have stringent power
and bandwidth limitations. This put renewed emphasis on finding
cryptosystems that were thrifty with both computation and
transmission. At the same time, there was growth in theoretical
knowledge, which led to breaking of numerous systems, and required
increases in key sizes of even well-trusted schemes such as RSA.
The outcome of the developments in technology and science is that
today we are witnessing explosive growth in applications of
sophisticated mathematics in cryptology. This volume is a collection
of both surveys and original research papers that illustrate well the
interactions of public key cryptography and computational number
theory. Some of the systems discussed here are based on algebra,
others on lattices, yet others on combinatorial concepts. There are
also some number theoretic results that have not been applied to
cryptography yet, but may be in the future. The diversity of
techniques and results in this volume does show that mathematics, even
mathematics that was developed for its own sake, is helping solve
important problems of our modern society. At the same time,
mathematics is drawing valuable inspiration from the practical
problems that cryptology poses.