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.