This document has been archived.

NATIONAL SCIENCE FOUNDATION
4201 WILSON BOULEVARD
ARLINGTON, VIRGINIA 22230

Report of the Working Group on Cryptology and Coding Theory National Science Foundation, April 17-18, 1997

October 14, 1997

Dear Colleague:

The increase in computer power and connectivity has changed the face of science and engineering, just as it has generated new opportunities for all Americans. We are entering an era in which information is available to anyone, located anywhere, at any time. As such we are faced with the challenge of understanding and managing larger and more complex systems in natural, social, material, financial and manufacturing spheres.

Over the past year, the Division of Mathematical Sciences has been exploring ways in which mathematical scientists might contribute to this challenge. There are many. For example, the transmission, organization, representation, control, presentation, security and integrity of data are central to modern communications, computing and networking and very clearly require involvement of mathematical scientists. The latter two, security and integrity of data, have been developed primarily by the security sector, and more recently, by industry. Academic research has not included cryptography and coding theory in a major way. So although both cryptography and coding theory are areas in which mathematical scientists can make, and have made, important contributions, the Division questioned whether there was a niche that could be filled by academic mathematical scientists.

The Division sponsored a workshop on cryptography and coding theory on April 17-18, 1997. The participants included researchers from the security sector, industry and academics. The outcome of the workshop was a report outlining the state and future of these areas as envisioned by this working group. The report of this working group is enclosed. The Division welcomes proposals in these general areas. In particular, proposals joint with computer scientists are considered highly appropriate. These proposals can be submitted to the Algebra & Number Theory program.

Sincerely,

Donald J. Lewis
Director
Division of Mathematical Sciences

Enclosure

This is a report of a special emphasis panel. The opinions, findings, conclusions or recommendations expressed in this report are those of the participants

On April 17-18, the National Science Foundation hosted an impressive panel of outstanding mathematicians with a remarkable record of contribution to two of the most fascinating and important application areas of the past half century: cryptology and coding theory. Included among the panelists were two of the three creators of L-cubed (the algorithm that most effectively "broke" the knapsack cryptography and continues to produce surprising results against a host of cryptologic problems); pioneers in the creation of algebraic coding theory whose algorithms have been vital to both cryptology and coding theory for over three decades (and still are!); and industrial scientists whose algorithmic breakthroughs are incorporated in hundreds of billions of digital-processing chips worldwide. Although they had a distinguished past, these panelists were forward-looking and extremely enthusiastic about the future -- but they had concerns. Their report follows.

1. Introduction.

Cryptology and Coding Theory. We are bullish on the continuing importance of cryptology and coding theory well into the next century, the number of problems that need to be solved, the importance and the elegance of the mathematics needed for solutions. Cryptology is a classical subject that traditionally guaranteed (or sought to undo the guarantee of) confidentiality and integrity of messages, but the information era has expanded the range of applications to include authentication, integrity and protocols for providing other information attributes, including timeliness, availability of service and protection of intellectual property. Cryptology has always been a charming and an exciting study, enjoyed by mathematicians and non-mathematicians alike. The recent breakthrough discovery of public key cryptography has been one (but not the only) contributor to a dramatic increase in the sophistication and elegance of the mathematics used in cryptology. Coding theory enables the reliable transmission and storage of data. Thanks to coding theory, despite dramatic increases in the rates and volumes of bits transmitted and the number of bits stored in computers or household appliances, we are able to operate confidently under the assumption that every one of these bits is exactly what it is supposed to be. Often they are not, of course, and the errors would be catastrophic were it not for the superbly efficient detection and correction algorithms clever coding theorists have created.

Discrete Mathematics: Applied Mathematics for the Information Age. During our April workshop, we reviewed five decades of exciting interaction between mathematics and these two fascinating and important subjects. In sections 3 and 4, we provide brief histories of cryptology and coding theory, in which mathematical constructs, mathematical subject matter, and sophisticated mathematical treatments have been critical to the solution of the most important practical problems. Although some continuous mathematics has been employed (notably, probability theory), the bulk of the mathematics involved is discrete mathematics. Yet, despite the strong testimony that cryptology and coding theory provide, there is little understanding or recognition in the mainstream mathematics community of the importance of discrete mathematics to the information society. The core problems in applied mathematics after World War II (e.g., understanding shock waves) involved continuous mathematics, and the composition of most applied mathematics departments today reflects that legacy. The increasing role of discrete mathematics has affected even the bastions of the "old" applied mathematics, such as the aircraft manufacturers, where information systems that allow design engineers to work on a common electronic blueprint have had a dramatic effect on design cycles. Meanwhile, mathematics departments seem insulated from the need to evolve their research program as they continue to provide service teaching of calculus to captive populations of engineering students. But the needs of these students are changing. As mathematicians continue to work in narrow areas of specialization, they may be unaware of these trends and the interesting mathematical research topics that are most strongly connected to current needs arising from the explosion in information technology. Indeed, a great deal of important and interesting mathematics research is being done outside of mathematics departments. (This applies even to traditional applied mathematics, PDE's and the like, where, as just one example, modeling has been neglected.)

The Role of Mathematicians. In the history of cryptology and coding theory, mathematicians as well as mathematics have played a prominent role. Sometimes they have employed their considerable problem-solving skills in direct assaults on the problems, working so closely with engineers and computer scientists that it would be difficult to tell the subject matter origins apart. Sometimes mathematicians have formalized parts of the problem being worked, introducing new or classical mathematical frameworks to help understand and solve the problem. Sophisticated theoretical treatments of these subjects (e.g., complexity theory in cryptology) have been very helpful in solving concrete problems. The potential for theory to have bottom-line impact seems even greater today. One panelist opined that "this is a time that cries out for top academicians to join us in developing the theoretical foundations of the subject. We have lots of little results that seem to be part of a bigger pattern, and we need to understand the bigger picture in order to move forward." But unfortunately, the present period is not one in which research mathematicians are breaking down doors to work on these problems.

Mathematicians are clearly needed to create mathematics. It is less clear that they are indispensable to its application. One panelist pointed out that there are many brilliant engineers and computer scientists who understand thoroughly not only the problems but also the mathematics and the mathematical analysis needed to solve them. "It's up to the mathematics community," he continued, "to choose whether it is going to try to play or whether it is going to exist on the scientific margins. The situation is similar to the boundary where physics and mathematics meet and mathematicians are scrambling to follow where Witten and Seiberg have led."

Another panelist disagreed, believing it highly desirable, if not necessary, to interest research mathematicians in application problems. "When we bring in (academic research) mathematicians as consultants to work on our problems, we don't expect them to have the same bottom-line impact as our permanent staff, because they will not have adequate knowledge of system issues. However, in their effort to understand our problems and apply to them the mathematics with which they are familiar, they often make some unusual attack on the problem or propose some use of a mathematical construct we had never considered. After several years and lots of honing of the mathematical construct by our 'applied mathematicians,' we find ourselves in possession of a powerful and effective mathematical tool."

Why Mathematicians Should Play (with applications). There are reasons that (academic) mathematicians should be eager to engage these fascinating problems in addition to the possibility that they might contribute to solutions. These include:

(1) Natural curiosity. A scientist should "care" about how his science is applied.

(2) Timeliness. Application work is always exciting, but it is especially exciting to be part of the connection between mathematics and the dawning of the information era, which is impacting every aspect of our society.

(2) Pedagogy. Familiarization with applications is valuable in the classroom but often missing. An explanation or description of how a mathematical concept is applied can be extremely useful in making the concept clearer. Also, students may be impressed (and pay more attention) if the abstraction can be shown to have immediate real-world consequences. (In sections 3 and 4 we refer briefly to expositions that have been useful in making these links for undergraduates, and, in the case of Sinkov's 1966 MAA expository publication, for high school students.)

(3) Mentoring. Most students will not follow their professors' career path. Faculty can most effectively prepare their students for future employment if they are knowledgeable in both mathematics and applications.

(4) Networking. It is even better for the student should his or her professor know potential employers. What better way to know them than to have worked on common problems of interest or, even better, with the employers directly?

(5) Serendipity. Although proud of its pristine, abstract nature, mathematics' origin is in real-world problems, and the development of mathematics has been enriched by brushing against real-world problems. Mathematicians advertise extensively that through some serendipity, mathematics solves real-world problems. The converse, that real-world problems can inspire important new mathematics, is also true.

Why Mathematicians Don't Play. We could not agree as to the primary reasons more academic research mathematicians did not work on applications (or, in particular, on our applications). We listed a number of likely causes. We would be eager to have a National Science Foundation program attack these causes head-on.

(1) Mathematicians focus on narrow specialties, at first to get worthy results, later to gain recognition, tenure and funding. Career pressures make it difficult to take the time to learn even about interesting work in other fields of mathematics. Mathematicians wishing to contribute to applications must learn a substantial body of application material, an eclectic collection of mathematical approaches to analyze the subject matter and the special issues and requirements posed by the information age. This is a daunting task, indeed. Little in the current reward system encourages mathematicians to take this task on.

The pressures inhibiting involvement with applications are most pronounced on younger faculty. Ironically, they are more likely than their senior colleagues to have more familiarity with the applications and relevant computational techniques which could be useful in analysis.

(2) Most of the mathematical research community in the U.S. does not look outside their own mathematical field for a source of problems to work on. Most of what today is regarded as "applied mathematics" was developed over many years as researchers applied their knowledge of continuous mathematics to models of physical processes. This rich tradition has been slow to take hold in other fields and, in particular, to the problems of the information age.

(3) There is relatively little basic research support to encourage mathematicians to work on our problems. In spite of strong evidence during the past ten years of interesting and compelling problems of national interest, relatively little funding has been identified specifically for cryptologic research.

(4) For whatever reason, funding agencies and consumers for other branches of applied mathematics, such as control theory or finite element analysis, seem to be able to separate off the parts of their mission that are sensitive (or proprietary or secret) and require controls on the publication of mathematical research. A lack of "open problems" is a disincentive for young mathematicians to work on a subject in which they cannot publish openly. "Secrecy and the pursuit of knowledge for its own sake are uneasy bedfellows."--James Conant (1952).

The Reasons. We are very enthusiastic about efforts on the part of the National Science Foundation to encourage mathematicians to learn about and contribute to application problems for all of the following reasons:

to help mathematicians understand the power and relevance of the abstractions they have created;

to help mathematics departments understand how they should evolve curricula to better prepare students for the information era;

to enable graduate students to gain experience on important real-world problems, and understand the applicability of mathematical abstractions to these problems, under the tutelage of experienced faculty;

to help faculty be better positioned to help graduates find relevant employment that makes best use of their mathematical training;

to contribute new ideas to subjects that regularly make use of mathematical constructs to solve practical problems;

to inspire more research in emerging mathematical topics that have proved especially relevant to the information era.

Because of the importance of information integrity (one of several ways of combining cryptology and coding theory) to the information age and of discrete mathematics to information integrity, we are, in particular, even more enthusiastic in encouraging you to sponsor research on these problems that we have found to be so much fun to work on.

Missions. We spent a brief period worrying whether in-house or external work sponsored by mission agencies (including the National Security Agency) or industry satisfied the needs we are asking the National Science Foundation to address. We are convinced they do not. The missions of the NSA and industry are limited. There are a number of important, fundamental problems that do not fit into NSA's mission and that are too early in their development to be of interest to industry. Much of the anticipated cryptologic research has the potential to impact national security, but there are national interests in the information age that are not covered by a traditional national security mission. Information now has an impact on every aspect of human life, including our social institutions, our political stability and our economic growth and stability. Some examples of problems of national interest that fall outside the scope of traditional national security include the ability to enforce taxation in an electronic commerce setting, the ability to extract medical information from records without compromising the privacy of individuals and the ability to protect free speech in an electronic age.

Mission agencies and industry have very natural but restrictive rules for conduct of sponsored research projects, derived from the nature of their mission. Universities have the role and mission to produce fundamental technology and are unique in their ability to enable the public at large to benefit from the work while simultaneously guaranteeing the discoverer the appropriate benefits she or he deserves. (See also recommendation (9) following.) And even were it not necessary for universities to be involved in this research, it would be unfortunate were they not, for the several reasons we listed in the introduction and earlier in this section.

Commitment. Sections 3 and 4 suggest a number of important open problem areas that could benefit from study by (academic) mathematicians. As an exercise, during our deliberations in April, we "brainstormed" a number of specific problems and found the list to be extensive. We do not view ourselves as an exclusive source of wisdom on what needs to be done, but we went through this exercise to show not only that such problems exist, but that we were willing and committed to provide guidance to anyone interested in helping us move the frontiers of these fields forward. We are personally committed to serving as part of any peer-review process you find useful and believe you will find many other equally qualified folks who will be eager to help.

Specific Recommendations. We are not aware of all the opportunities available through NSF funding. We were not able, in the limited time that we had, to learn (from NSF's most recent experiences) what works and what doesn't. We will not try to outline a program but will make a few specific suggestions. We will be pleased to review any proposals NSF originates.

(1) We encourage construction of programs in which university mathematicians work with members of other departments in NSF-funded research or to give "extra credit" for proposals that intend to do this. The Division of Mathematician Sciences should encourage mathematicians to seek out such opportunities, and it should work with other parts of the National Science Foundation to encourage other departments to seek out mathematics faculty or graduate students to work jointly on problems in an applied area. Typically, it is easier for the initial identification and understanding of the problem to come from an area other than mathematics.

(2) Despite recommendation (1), it is important to reserve significant funding for "primary investigators" who are good mathematicians with solid proposals, whether or not they have connections with other departments . You should have confidence that your peer review board will be eager and able to help these mathematicians focus their work in relevant directions on relevant problems.

(3) It will be natural to also give "extra credit" to proposals that directly impact specific cryptologic or coding theory problems. However, it is also important to encourage work on problems believed to be important by those who work directly on application problems. Although the latter is a "half-way" step, half a step is better than no step at all, and the work might well provide a valuable transition for the researcher. (Your peer review board must be vigilant in rooting out proposals where the connection to the application is secondary or contrived.) However, any research proposals of this second kind should guarantee the willingness of the investigator to familiarize himself or herself with the source problem and the effect of his or her results on the problem.

(3) The Division of Mathematical Sciences should work with the other appropriate divisions of the National Science Foundation and the most important professional societies in cryptology and coding theory in the construction of their program. Cryptology has an especially enthusiastic international society, the president of which was one of our panelists.

(4) Programs that provide research mathematicians opportunities for part time or full time (sabbatical) involvement with government or industry are especially desirable. We are aware that similar programs (with a more general focus than cryptology and coding theory) are undersubscribed. Perhaps NSF priorities and funding can help reverse this, either directly or indirectly by "gently persuading" department chairmen or physical science deans.

(5) Some of us believe that a portion of your program should actively seek out mathematicians who have not been involved in this work. Others worry that an emphasis on "first involvement" encourages dilettantes. This remains an open issue.

(6) An AMS short course [Boulder, 1989] and the proceedings issued from this course were extremely useful in exposing mathematicians to cryptology. Meetings and workshops should be actively sponsored.

(7) The National Science Foundation should encourage university courses in cryptology and coding theory, and the Division of Mathematical Sciences should encourage the involvement of mathematics faculty in these courses. It will not always be the case that the mathematics department is the appropriate site to center the study, since important implementation and system issues are probably better understood by computer science or communication engineering departments. However, the involvement of mathematics faculty is vital for insuring that students understand, where appropriate, the mathematical concepts involved and the potential for further generalization in directions most likely to impact further on the problem. Collaborative teaching with faculty from other disciplines would provide an opportunity for mathematics to build bridges to other departments.

(8) Good courses will, of course, lead to better textbooks and other appropriate expositions. The current state of textbooks is improving, but more improvement is needed.

(9) Fundamental research that furthers our understanding of important security issues that do not impact "national security" will be inhibited if subject to the same restrictions appropriate to the national security mission. The National Science Foundation program should be subject only to the controls placed on other NSF-funded research.

Conclusion. We, like you, are extremely respectful of academic freedom. We are also aware of the wonderful serendipity by which mathematics created to solve purely mathematical problems turns out to be just as useful to the solution of applied problems as does mathematics created solely to solve real-world problems. Still, it has been important for mathematics to brush against real problems throughout its history, and it is certainly important for our graduate students to have success in applying mathematics to real-world problems under the tutelage of professors knowledgeable in both mathematics and applications. A new initiative to investigate the mathematical foundations on the integrity of information is timely indeed! We appeal to you not to err in the direction of conservatism in creating, sponsoring and funding new programs that will encourage university mathematicians to join us in important and exciting work.

Some (very brief) History. Even though there has been a dramatic increase in the elegance and sophistication of the mathematics employed in modern cryptology, mathematicians historically have played a vital role in making and "breaking" codes. The Polish, British and U. S. cryptographic efforts that contributed greatly to the Allied victory in World War II illustrate this. The initial breakthrough against the Enigma, the workhorse diplomatic encipherment system employed by the Germans in World War II, was effected by three brilliant Polish graduate mathematicians (in an application of elementary group theory); and Turing, Whitehead and Newman among others provided the Allied forces the ability to read substantial portions of German "secret" communication despite a number of security upgrades. Across the Atlantic, Gleason, Hall and Albert made important contributions to the total cryptanalytic effort, while Kullback and Sinkov were among the "inner circle" that helped Friedman take on Japan's cryptographic systems. The Japanese were more sensitive than the Germans to the possibility that their secure communications could be exploited, and to guard against this they changed the basic cryptographic workings of their devices at the slightest suspicion of Allied success. As a result, although American cryptanalysts made excellent breakthroughs and gained considerable insight into Japanese operations, they could not do so with the same degree of continuity "Enigma breakers" enjoyed against German targets. Despite these difficulties, what enciphered communications were read played a major role in the Pacific War. Admiral Nimitz and others highly valued our codebreakers for their unique ability to get inside the enemy's mind.

Conversely, the excitement of cryptology has stimulated young people to study mathematics and has provided important illustrative examples of the power and utility of mathematical ideas, constructs and theories (e.g., Sinkov's 1966 MAA expository publication introduced the concept of matrices to high school students through affine codes). The "index of coincidence" (developed by Friedman's group as a tool in breaking complicated substitution ciphers) and extensive analysis of the Army's Hagelin M209 cryptography in the public literature highlighted the role of probability and statistics in codebreaking, and the importance of shift registers and similar algebraic components in electronic cryptography did the same for abstract algebra. The National Security Agency (NSA) provides strong evidence that both mathematics and mathematicians have continued to be vital to cryptology for the five decades following World War II. NSA is the world's largest employer of mathematicians and continues a significant effort to supplement NSF funding for pure mathematics despite shrinking resources.

Public Key Cryptography. In the late 1970s, a small group of brilliant academic cryptographers proposed a series of elegant schemes through which secret messages could be sent without relying on secret variables (key) shared by the encipherer and the decipherer, secrets the maintenance of which depended upon physical security, which historically has been often compromised. Instead, in these "public key" schemes, the message recipient published for all to see a set of (public) variables to be used by the message sender in such a way that messages sent could be read only by the intended recipient. (At least, the public key cryptographers hoped that was the case!) It is no exaggeration to say that public key cryptography was a breakthrough "of monumental proportions," as big a surprise to those who had relied on conventional cryptography in the sixties as television was to the public in the fifties.

Breaking these "public key" ciphers requires, or seems to require, solutions to well-formulated mathematical problems believed to be difficult to solve. One of the earliest popular schemes depended on the solution of a certain "knapsack" problem (given a set of integers and a value, find a subset whose constituents sum to that value). This general problem was thought to be hard (known to be NP- complete), but a flurry of cryptanalytic activity discovered a way to bypass the NP-complete problem, take advantage of the special conditions of the cryptographic implementation and break the scheme, first by using H. Lenstra's integer programming algorithm, next using continued fractions, later and more effectively by utilizing a lattice basis reduction algorithm due to Lenstra, Lenstra and Lovasz. Although many instantiations of public key cryptographies have been proposed since their original discovery, current cryptographic implementers seem to be placing many of their eggs in two baskets: one scheme (Rivest-Shamir-Adleman, RSA), whose solution is related to the conjectured difficulty of factoring integers, the second, (Diffie-Hellman, DH), which is related to the conjectured difficulty of solving the discrete logarithm problem (DLP) in a group. The discrete logarithm problem in a group G, analogous to the calculation of real logarithms, requires determination of n, given g and h in G , so that gn = h.

Each of the past three decades has seen significant improvements in attacking these schemes, although there has not yet been the massive breakthrough (as predicted in the movie "Sneakers") that would send cryptographers back to the drawing boards. The nature of these attacks leads some to suspect that we may have most of our eggs in one basket, as most improvements against RSA seems to correspond to an analogous idea that works against the most common instantiations of DH (when the group is the multiplicative group of a finite field or a large subgroup of prime order of the multiplicative group) and vice versa. Asymptotic costs to attack each scheme, although each has declined as a consequence of new algorithms, continue to be comparable. These new algorithms, along with improvements in computational power, have forced the use of larger and larger key sizes (with the credit for the increase split about equally between mathematics and technology). As a result, the computations to implement RSA or DH securely have been steadily increasing.

Recently, there has been interest in utilizing the elliptic curve group in schemes based on DLP, with the hope that the (index calculus) weaknesses that have been uncovered in the use of more traditional groups will not be found. It is believed, and widely marketed, that DLP in the group of points of non-supersingular elliptic curves of genus one over finite fields does not allow a sub-exponential time solution. If this is true, DH in the elliptic curve group would provide security comparable to other schemes at a lower computational and communication overhead. It may be true, but it certainly has not yet been proven. There are connections between elliptic curve groups and class groups with consequences for the higher genus case and extension fields. In particular, Menezes, Okamoto and Vanstone [1991] showed how the Weil pairing gave a better method for solving DLP for a particular class of elliptic curves, the supersingular ones. These are curves of order p+1, and DLP is reduced to a similar problem in GF(p2), where it can be more effectively solved. Work continues in an effort to extend these results to the general curve group.

A related problem in elliptic curve cryptography focuses attention on another possible exciting interplay between theoretical mathematics, computer science (algorithms) and practical implementation. Calculation of the order of the elliptic curve group is not straightforward. Knowing the order of their group is very important to DH cryptographers, since short cut attacks exist if the order of the group factors into small primes. Current elliptic curve cryptosystem proposals often employ a small class of curves to circumvent the counting problem.

Even less progress has been made on the more general problem of whether there exist any groups whose DLP is exponential and, if so, characterizing such groups. Another interesting problem is whether solving DLP is necessary as well as sufficient for breaking DH. There are some groups for which this is known to be true, but determining whether this is true for all groups, or characterizing those groups for which it is true, remains to be done. A third interesting general DH problem is "diagnosis" of the DH group (when one has intercepted both ends of DH exchanges and does not know the group employed).

Broadening Applications and Strong Growth in Demand. Originally intended for classical cryptographic applications (communicating secret messages), public key cryptography ideas proved easy to modify for other important needs in modern society, in which millions of paper transactions have been replaced by the rapid flinging and storing of trillions of bits of information. Variants of public key cryptography are now used to provide valid electronic signatures, authentication schemes (which insure the message has not been tampered with and originated from the appropriate transmitter), identification schemes (ATM and other smart cards provide strong demand for this application) and secret-sharing schemes (e.g., algorithms that allow a sufficient majority of decision makers to automatically effect an action). This last had its origins in nuclear weapon use control but is now an issue in processing network commerce.

Interest in applying these schemes is certainly growing. Every month Wall Street brings an initial public offering of some new start-up with "trusted" or "security" in its name, and although these are primarily engineering companies, they are expanding the quality of protection they provide by employing more sophisticated and pervasive encryption. Trade shows in cryptologic products are increasingly "hot tickets"; attendance at one prominent one has approximately doubled every year for the past five years. With commercial encryption still an infinitesimal fraction of the economy and demand growing, it is not unreasonable to expect exponential growth in demand to continue for several decades. Although implementation issues dominate (and, to a lesser extent, litigation issues, as patents are hotly debated), the leading companies (including Cylink, which holds the DH and other Stanford patents, as well as RSA Data Security, now a subsidiary of Security Dynamics) continue to hire a significant number of mathematicians as well as computer sciences and engineers. Although the more typical industrial security company is not interested in inventing new ideas, it still needs to hire mathematicians to understand the technology available and to tailor it to its particular applications. One of our panelists recently accepted a position with a major bank as its security guru. "My experience is that industry is taking cryptology seriously and wants to hire top mathematicians to help them understand what they need. Industry doesn't necessarily understand what a mathematician does, but they want the best. I don't believe they would be satisfied with a bachelor's level background, even though they don't necessarily know how to use someone with a master's level or Ph.D. background. Still, I think industry might be right. The deeper training in mathematics is likely to pay off in some unexpected way. But that depth must be accompanied by some academic experiences that provide breadth, or the graduate will flounder in the industrial environment."

Traditional Symmetric (Secret) Cryptography. Because asymmetric (public key) encryption schemes are more computationally demanding than secret ones, asymmetric encryption is often used by communicators to exchange secret variables that are then used as keys for traditional symmetric encryption to encipher long messages. Examples of such algorithms are block ciphers, of which the Data Encryption Standard (DES) is the best known, and stream ciphers, which typically employ feedback shift registers among other components..

DES is a cryptography that has been well-studied (others are IDEA and FEAL). Although twenty years of analysis have failed to produce a practical sub-exhaustive attack on DES, work by Biham and Shamir and by Matsui has come close and in the effort discovered two promising new classes of attacks (differential and linear cryptanalysis, respectively).

Stream ciphers obtained from feedback shift registers have been studied profitably for three decades. The mathematics involved includes finite field theory, combinatorics, projective geometry and algebraic geometry. Shift register sequences continue to be important components of modern cryptologic systems. Also, because of their good correlation properties, they are the foundation of the design of modern spread-spectrum communications (difficult to intercept, difficult to jam transmissions). They are strong candidates for use in the booming cellular phone communications market.

Study of traditional symmetric cryptography has been hampered by a lack of specific examples to be considered, although there are now a number of well-established shift register cryptographies and software encryption schemes that merit further work. Although analysis tends to be application-specific, significant attacks are constructed from probabilistic models of algebraic structures, an attractive mixture of fundamental mathematics that rarely interact in academic mathematics. Efforts to apply these attacks or develop new attacks against any of the many fast software encryption schemes or other traditional symmetric cryptographies would be valuable, not only for evaluating current candidates, but for developing an ensemble of attacks techniques and a framework for assessing the security of modern cryptographies.

Protocol and System Attacks. Most cryptanalytic successes do not require a devastating, deep theoretical breakthrough revealing an heretofore unanticipated weakness in a sophisticated encryption scheme. Rather, they typically result from some misuse of, or failure in, the cryptographic system, which is then detected, analyzed and exploited by a clever adversary. For example, the initial breakthrough against Enigma resulted from a weakness in the Germans' indicator procedure (which informed the receiver how to set his machine to receive a particular message), and recently some Berkeley graduate students were able to "break" Netscape's use of RSA by taking advantage of a failure to utilize all the bits in a random number generator. These are examples of insecure protocols (rules for the precise implementation of the encryption scheme), the moral of which is that it is not sufficient to use a "secure" cryptosystem in order to guarantee secure communication. One panelist believes that the reason that many vulnerabilities arise in this way is the failure of cryptologists to develop a mathematical framework for analyzing protocols comparable to that for analyzing the fundamental algorithm itself. Although protocols form the backbone of any cryptographic scheme, current analyses rely on heuristics rather than on well-defined formalism.

Other system aspects outside the protocols can also conspire to bring down an otherwise secure cryptology. More recently, Bellcore scientists coupled clever mathematics with models of the encryption process to propose a number of general fault-based attacks against modern public key schemes. This system-level model has opened a variety of new trapdoors through which codebreakers can slip. Perhaps the most striking example is due to Kocher, who discovered that by precisely timing the hardware operations needed to sign a well-chosen set of messages, he could break a wide variety of cryptosystems by recovering the secret keys. There are a number of other possibilities for system-specific attacks, and Biham and Shamir have developed similar system attacks against DES. (For more on this, see Paul Davis's excellent article in SIAM News, April, 1997.) But the value of system attacks does not limit the need to do theoretical research in cryptology. Indeed, the experience of both NSA (over five decades of classified research) and the relatively fledgling public effort is that top theoreticians play a key role in inventing, understanding and generalizing the more "practical," system-specific assaults on encryption schemes and, conversely, the experience gained in real attacks on real implementations provides motivation and insights for the continued development and improvement of general cryptologic theory.

Quantum Computing. Recently [1994] an interesting polynomial-time algorithm for factoring has been proposed by Peter Shor. One caveat: the attack cannot be carried out on a conventional computer but rather requires a "quantum computer." Quantum computation attacks the Church-Turing thesis (strengthened version) that Turing machines can compute efficiently anything that can be computed efficiently by physical devices. It was discovered by physicists in the mid-80s who were studying how quantum effects would affect calculations as computers were shrunk to atomic scale. To their surprise, the physicists discovered that such computers, with states described by a wave function rather than a discrete bit, had advantages over classical (Turing) computers, and could do some calculations (e.g., discrete transforms) very effectively (i.e., in polynomial time when there was no polynomial time algorithm on a classical machine). Shor takes advantage of this to concoct an algorithm that factors integers (and computes discrete logarithms) in time proportional to n2. Whether "quantum computing" will ever become practical for factoring or any other similar computational task will require substantial improvements in implementation over what can be done today, but further research is needed to determine whether quantum computing can compete against computers built in traditional technology, and application research as well as implementation research should be an important part of that study. What types of classical problems are amenable to quantum algorithms is an exciting question (e.g., is there a quantum algorithm for finding short vectors in lattices?). Serious efforts to describe and evaluate cryptanalytic attacks on quantum computers will be valuable not only as a contribution to cryptology but also as a forward-looking study of a potential emerging technology.

From pencil-and-paper to mechanical devices to electronic devices to semiconductors to microprocessor-based cryptographies to high-bit-rate systems, each family of technologies provides a capability both to make codes (cryptography) and break codes (cryptanalysis), typically in an equilibrium that encourages and rewards clever strategies. Consequently, we are also enthusiastic about the parallel subject "quantum cryptography," in which algorithms are designed for "quantum computers" that are hopefully resistant to cryptanalytic attacks mounted by either conventional or "quantum" computers. So many, many exciting problems to work on!

Introduction. While abstract algebra (then called "modern algebra") was proving to be the single most important tool for analyzing shift registers and similar components used in the cryptographies of the time, the early fifties also saw the birth of an important new application of discrete mathematics to one of the most important challenges facing technology of that time, a challenge even more critical today as more and more bits of information are flung into and out of the ether at increasingly rapid rates. Coding theory enables the reliable transmission and storage of data. This general framework includes the algebraic theory of error-correcting codes, where codewords are strings of symbols taken from some finite field, and it includes data transmission over channels subject to Gaussian noise, where codewords are vectors in Euclidean space. In less than five decades, coding theory has produced both interesting mathematical advances and vital real-world solutions. Initially fueled by elementary linear algebra and ring theory, coding theory became a source of important results and tools in incidence-structure combinatorics, while simultaneously proving to be both ubiquitous and indispensable in modern technology. The many advances in digital signals processing (of which coding theory provides a significant portion) is indeed the reason we have computers, hard-disc drives, satellites, compact-disc players and V.34 high speed modems. Innovation in coding and signal processing is often the difference between success and failure in the marketplace, and the revenue stream obtained by the successful corporation is huge.

Cyclic Codes. From the beginning of digital representation of quantities (both in computers and communication) came the need for high reliability at the highest possible speed. Shannon's Theorem [1948] predicted in a non-constructive manner that reliability for the digital domain can be achieved by introducing systematic redundancy into the data. Remarkably, the work of Hamming and Golay produced, within a year of Shannon's monumental paper (which virtually created the subject of information theory), two highly efficient codes still in use today. The discovery by Reed and Muller in 1954 of longer (RM) codes having feasible decoding algorithms led to the communications capability that enabled NASA's Mariner mission to transmit the first images of the surface of Mars in the 1970s. All subsequent NASA deep space missions successes were possible only because of the discovery and availability of increasingly sophisticated error-correcting codes. (One panelist points out that although these were spectacular accomplishments, the space channel is characterized by very low throughput and high tolerance of large signal processing delays. Consumer electronics is much more demanding in these respects.)

Bose, Ray-Chaudhuri [1960] and Hocquenghem [1959] independently introduced a particular class of binary codes, which soon became known as the BCH codes. Independently, Reed-Solomon [1960] introduced a similar class of nonbinary codes (the RS codes). No decoding algorithm for either BCH or RS was initially known, and the first one, published by Peterson more than a year later, was widely viewed as impractical. In 1968, Berlekamp (one of our panelists) published the first improved decoding algorithm for BCH and RS codes, based on generating functions rather than matrices, reducing one portion of the workload from cubic to quadratic in the number of errors corrected. For many years, RS codes, which work on bytes and other wordlengths longer than one, were considered more complicated than binary BCH codes, in that

(1) RS encoders require multiplications in nonbinary fields, and

(2) RS decoders must find both the location and the value of each erroneous bit, whereas BCH decoders need find only the location.

However, over the years, a long series of decoding algorithms for both RS and BCH were introduced, all of which so favored RS that by the late 1970s, well-designed RS decoders were substantially less expensive than BCH decoders of comparable performance. Yet, the need for RS codes to do considerable arithmetic in nonbinary fields still seemed a serious argument against their use in space communications, where the costs of the spaceborne encoder typically dominated the costs of the ground-based decoders. This situation was radically and surprisingly changed by Berlekamp's [1982] "Bit-Serial RS Encoders," which showed that, by careful choices of dual bases of the appropriate extension fields, one can design RS encoders that are substantially simpler than binary codes of comparable redundancy. RS codes have since been used in virtually all NASA deep space communications, including the Hubble space telescope. They have also become ubiquitous in such commercial consumer products as optical compact discs, magnetic tapes and magnetic discs. Even after 35 years of extensive study of these remarkable codes, significant improvements in decoding algorithms and architectures continue to appear.

The Hamming codes, RM codes, Golay codes, BCH codes and RS codes all are cyclic codes (invariant under cyclic shift). In some cases this property was not known to the inventors. Prange, working in the late 1950s at the Air Force Cambridge Research Labs (AFCRL), undertook early pioneering studies of the general properties of cyclic codes. Gleason and MacWilliams began a classification of self-dual codes by bringing into play an all-but-forgotten 19th century technique called invariant theory. MacWilliams (both in her 1962 thesis at Harvard and subsequent work at Bell Labs), through a clever use of generating functions, proved one of the most surprising results in algebraic combinatorics (the MacWilliams Identity). Important advances by Assmus (a panelist) and Mattson were published in the Journal of Combinatorial Theory [1969]; "new 5-designs" connected algebraic coding theory with finite geometry and introduced nontrivial connections with ordinary group representation and algebraic number theory that greatly increased the efficiency of these codes and their decoding algorithms. The Mattson-Solomon polynomial was a further breakthrough, describing the study of codes and designs as finite Fourier analysis. Not only did all this mathematics prove relevant in generating practical codes, but conversely, the combinatorial objects corresponding to these codes proved more interesting than those known previously. Less direct but still notable applications resulted from the study of lattices and sphere-packing, with the design of cellular phone systems a major beneficiary. Pioneering research texts in coding theory by Berlekamp [1968] and MacWilliams and Sloane [1977] have helped popularize the applicability of discrete mathematics, with the result that finite field theory and combinatorics are now a part of undergraduate curricula, although more typically taught in computer science and engineering rather than mathematics departments. (Panelists were quick to point out that these treatments belonged in other departments unless and until mathematicians understood the end applications.)

Challenges of the Nineties. In the nineties we face greater challenges, such as, for example, the problem of handling multi-user communication over a shared resource subject to both intersymbol and interuser interferences as well as noise, a much more complex problem than in the classical point-to-point communication over a noisy channel. The World Wide Web has attracted tens of millions of users, and portable computing is growing rapidly. While the number of mobile data users so far is small, the number of wireless data users is expected to grow rapidly in the near future. These users are likely to demand increasingly higher data transfer rates with web-servers. Advanced modulation, coding and antenna technology have the potential to make mobile web browsing a reality.

Modern Developments. Delsarte [1973] initiated development of theory that laid the groundwork for a number of new codes in the nineties. He quantified duality between packing and covering for codes and designs, which was followed by new and improved upper bounds (by McEliece and others) on achievable rate, by Lovasz's calculation of the Shannon capacity on the pentagon, and by the work of Wilson, Frankl and others on the Erdos-Ko-Rado theorem.

Paralleling both mathematics and cryptology (in each of these two, algebraic geometry is surging in its applicability), the nineties have seen the introduction of algebraic geometry codes. Algebraic geometry codes provide more flexibilities in choice (less limitations in codelength) and have superior performances at large length, although they require clever implementations. Following Goppa's pioneering use of algebraic curves to construct codes, Tsfasman, Vladut and Zink showed the existence of nonbinary linear codes that beat the Gilbert-Varshamov lower bound using results from algebraic geometry. The resulting very constructive dialogue between engineers and algebraic geometers helped Sakata, Justesen, Feng and Rao construct efficient decoding algorithms much better than geometers expected, because they took advantage of the special character of the curves involved.

Finding curves suitable for the construction of long codes is an important and broad research question. It is necessary to discover (in order) a curve with many rational points, an explicit characterization of its affine ring, a set of generators and relations that reduces the general decoding complexity, particular codes that make optimal use of the features of the curve and a feasible hardware architecture for coding and decoding. A number of promising curve-families are at various stages of this process. There are strong and fruitful links among algebraic coding theory, cryptography, curves over a finite field and exponential sums; and research motivated by algebraic geometry codes has obtained new results in all these areas.

Another promising generalization of the nineties is codes over rings, specifically the ring of integers modulo 2n, which began with the discovery by Hammons, Kumar, Calderbank (one of our panelists), Sloane and Sole that two celebrated families of nonlinear codes defined via quadratic forms were actually linear if viewed as codes over the ring of integers mod 4. This led to new code constructions, to different constructions for extremal unimodular lattices, to 2-adic analysis of binary codes and to connections with orthogonal/symplectic geometry.

An interesting theoretical problem of real practical interest is that of generating sequences of symbols that do not contain certain subsequences. In magnetic recording, the binary symbols 0 and 1 represent nontransitions and transitions, respectively. Disc-drive circuitry derives clock from transitions in the data, so long runs of zeros are forbidden. Other finite patterns lead to confusion at the output of the channel so are forbidden as well. Incoming data is mapped onto codewords by means of a finite state machine. An effective method for construction of the encoder for a given set of constraints was given by Adler, Coppersmith and Hassner building on early insights of Franaszek. AT&T built a $350M advanced read channel chip business from scratch in three years, and coding innovation was one of the keys. Everyone has an adequate CMOS process -- it's what you do with it that counts! This work on constrained coding also has deep and interesting connections with symbolic dynamics, linear systems and ergodic theory. (Our panelist who provided this information clearly believes magnetic recording is an important technology. Another, who agrees, worries that this huge, successful, technically innovative industry is unfortunately decoupled from academia, attracting far less academic interest (and financial support from DARPA and NSF) than justified by its economic and technological importance. But we have strayed from our primary topic, to which we now return....)

Issues in decoding complexity (e.g., constructing structured codes that would achieve Shannon capacity) have always been important, but for the most part these took a back seat to the exciting progress in more algebraic constructions. Recently, however, Conway, Sloane, Forney, Vardy began an important investigation of finite state machine descriptions of codes and lattices with the aim of reducing the complexity of soft decision decoding. The starting point for all this was the groundbreaking invention of trellis coded modulation (the mathematics behind the V.34 modem) by Ungerboeck. Ungerboeck's breakthrough involved convolutional codes (generated by finite state machines) rather than block codes, with a key change of emphasis, measuring performance as a function of decoding complexity rather than block length. This led Calderbank, Sloane and Forney to a mathematical framework for trellis coded modulation based on lattices in Euclidean space. A second recent development fixes the complexity of decoding and seeks to maximize transmission rate. Spielman uses expander graphs to construct asymptotically good linear error correcting codes that can be decoded in linear time. Spielman's codes turn out to be one particular example of an ensemble of "low-density parity check codes" that were introduced and studied by Gallager in the early 1960s. Perhaps the most important research challenge in decoding is to achieve a sound mathematical understanding of why iterative decoding techniques work so well -- in particular, the extraordinary performance of the "turbo codes" constructed by Berrou, which come close to Shannon capacity on a number of channels. In "turbo codes," information bits are encoded, interleaved, encoded again, and the results of one round of decoding influence the decoding metrics for the next round. There has been some interesting additional work by McEliece and Hagenauer on "turbo codes," but the subject seems wide open for further analysis by those with an expertise in applied probability. In 1990s research, the designer of codes has been much more aware of hardware and (error) environmental issues, but this "practical" point-of-view has not diminished the substance and elegance of the mathematics involved. Also, surprisingly, the notions of theoretical computer science (a subject that did not exist when coding theory was first invented) proved useful in the study of these very "practical" algorithms.

Connections with Cryptology. Not surprisingly, given their common base in discrete mathematics and theoretical computer science, work on cryptology has affected coding theory and vice versa. We list only a few of many examples:

(1) the study of polynomials over GF(2), critical to the generation of codes and the construction and analysis of linear registers and spreading sequences;

(2) Berlekamp's clever algorithm for factoring polynomials over GF(2): it had immediate application to the study of shift registers, and the idea behind it reverberates throughout modern cryptology in attacks on DLP and RSA;

(3) several important cryptologic systems are based on codes, most notably, McEliece's scheme employing Goppa codes;

(4) the use of codes/designs to improve algorithmic efficiency (e.g., to limit the number of random bits used by probabilistic algorithms);

(5) the use of codes to obtain characterizations of traditional complexity classes, such as NP and PSPACE;

(6) the use of codes in cryptographic protocols, such as bit commitment and digital signature schemes;

(7) the application of sequences with good correlation properties to the design of spread-spectrum communications (difficult to intercept, difficult to jam transmissions).

Clearly, applied discrete mathematics is a single subject, with cryptology and coding theory providing a major part of the application motivation.

Quantum Error Correction. We ended the last section with a brief comment on quantum computing and its relation to cryptology. We shall do the same here. Our group believes that if "quantum computing" is ever to become a serious computational tool, the construction of effective error correction is among the most vital problems that must be solved. Two important research accomplishments have been the development of quantum error correcting codes (that allow reliable computers to be assembled from less reliable components) and development of a rudimentary theory for fault-tolerant computation. Although all this work has been carried out at industrial or government laboratories or physics and computer science departments, there are a host of important open mathematical problems, many of which are similar to problems we have discussed previously. These include finding the shortest vector in a lattice, packing problems in a Euclidean geometry and one very prominent research problem (related to one in our discussion of "codes over rings") in orthogonal/symplectic geometry.

We conclude with a few random comments during our two-day discussions which may reinforce or provide more background for some of the observations and conclusions in this report yet did not fit in the narrative of the prior four sections:

"I no longer feel I am a mathematician. Let me make clear what I mean by that. It's not that mathematics itself, or what I learned from mathematics, is no longer valuable. At times my work requires subject-matter knowledge that is different from mathematics. At times my work requires a different kind of creativity and problem-solving that is related to, but different from, mathematics. But there are critical times when mathematical subject matter and mathematical style (the ability to generalize, to prove theorems ) are vital. Why I feel estranged is that so few academic mathematicians are interested in what I do."

"I am now working for a major financial institution as their 'security guru.' I often find problems that are right up the alley of specialists in a number of core mathematical areas. I'm in a position to hire these experts on a part time basis as consultants. But, sadly, I can count on one hand the research mathematicians I can get to work on these problems. I'm sorry for those who are unwilling. I don't understand why they are not more interested in natural extensions of their academic work that the "real world" believes is important. They should show more interest, if not for themselves, then for their students."

"You're right that it would help their students. Chemistry, physics and computer science majors who do not stay in academics often get good first jobs through their thesis advisors. Not only do mathematics professors lack such contacts, they don't keep track of their students who end up working in industry."

"We need the most prominent mathematicians in the nation, the 'establishment,' to show more interest in these problems. Their failure to do so reinforces a caste system, with industrial mathematicians clearly on a lower rung."

"Codebreaking is exciting, mathematics is exciting, but for me what is most exciting is the interaction between theory and the problem itself. Typically, the initial mathematical result is interesting but not relevant. Both the theory and the problem help us understand what is needed, leading to new theory. Sometimes, the old theory then becomes relevant to some new problem. The interaction is fascinating, as well as very healthy."

"I agree. It is very important to be willing to 'get your hands dirty' with the details of the problem. This requires a willingness to learn new subject matter as it comes up. Yet, I have found that once a mathematician provides that willingness, he or she often understands the details of the problem as well or better than engineers, who have a more functional approach."

"Working on a real problem helps us become more eclectic in mathematics. Although many of the 'great' mathematicians have been eclectic, the average mathematician tends to cling to his or her particular area throughout a lifetime. I began to work on a problem in cryptology emphasizing a direction that seemed to require my field of specialization, but I then learned that another field was believed to have more promise. I obtained a result applying that second field. I now have some research interest in that second field and look forward to teaching a course in it."

"Mathematicians who make important contributions in these fields gain a real appreciation from leading scientists in other disciplines. Physicists and engineers know that mathematics is important, but do they know that mathematicians are important unless they see evidence of mathematicians helping them? I was struck by a glowing review by Forney (one of the most creative engineers of his generation) of a paper by Conway and Sloane. He loved those guys!! In hard times, you need all the friends you can get."

"I am an academic mathematician by origin, now teaching in a computer science department. I have a great interest in cryptology, publish regularly, and teach a course (in cryptology). My biggest regret is not being able to attract the better mathematics majors into the course."

"I believe she is observing a fundamental asymmetry between mathematics and computer science. The best computer science majors take mathematics courses, but the best mathematics majors never take computer science courses."

"I have a good friend, a solid mathematician who I'm sure could make some contribution to my work, who tells me that Diffie-Hellman provides the single most powerful argument to his liberal arts students that mathematics is important. He has congratulated me for working in an area where such a new, practical application has been found for such a fundamental idea as exponentiation. I suggested he work with me on a part time basis. He turned down my invitation, because he is seeking tenure and his department chairman would give him no credit whatsoever for such work."

"That's consistent with our (NSF) experience in the GOALI program (sabbaticals to government or industry for academics). We believe it is an excellent opportunity to gain real-world experience, but it remains undersubscribed."

"The National Security Agency instituted a sabbatical program about eight years ago. Participants have been effusive in their praise of the experience, both for what it has meant to them personally and how it has affected their subsequent teaching. Yet, like the NSF program, this opportunity has been quite undersubscribed. It has been especially difficult to attract younger career-track academicians."

"There has been a lot said here about how good some real-world experience would be for the professional health of faculty and job opportunities for students. I don't dispute any of that. But I would like to emphasize how good more involvement would be for the field (cryptology) itself. I sense that we (cryptographers and cryptanalysts) have been playing on the margin. I'm proud of our work. We have formulated good problems and good algorithms and made dramatic improvements in cryptanalytic capabilities, but I think that the subject cries out for theory. Perhaps it always seems that way, but that is my sense, as one who has worked hard on applications for two decades. We might well be in a position to learn a great deal from the leading academicians as well as teach them something."

The Foundation provides awards for research and education in the sciences and engineering. The awardee is wholly responsible for the conduct of such research and preparation of the results for publication. The Foundation, therefore, does not assume responsibility for the research findings or their interpretation.

The Foundation welcomes proposals from all qualified scientists and engineers and strongly encourages women, minorities, and persons with disabilities to compete fully in any of the research and education related programs described here. In accordance with federal statutes, regulations, and NSF policies, no person on grounds of race, color, age, sex, national origin, or disability shall be excluded from participation in, be denied the benefits of, or be subject to discrimination under any program or activity receiving financial assistance from the National Science Foundation.

Facilitation Awards for Scientists and Engineers with Disabilities (FASED) provide funding for special assistance or equipment to enable persons with disabilities (investigators and other staff, including student research assistants) to work on NSF projects. See the program announcement or contact the program coordinator at (703) 306-1636.

The National Science Foundation has TDD (Telephonic Device for the Deaf) capability, which enables individuals with hearing impairment to communicate with the Foundation about NSF programs, employment, or general information. To access NSF TDD dial (703) 306-0090; for FIRS, 1-800-877-8339.

NSF 98-14