The Mathematics of Communications: keeping secrets

        For thousands of years people have tried to communicate secretly and securely. Cryptography is the field of mathematics dedicated to exploring schemes to conceal messages and to verifying the difficulty of "breaking" these schemes: that is, revealing the hidden message without the consent or knowledge of those communicating.
        This course will discuss some of the mathematical and social issues related to cryptography. Historically most cryptographic investigation was done by governments and these efforts were rarely publicized. They were massive: the largest single employers of mathematically trained people in the United States and the former Soviet Union have been the government agencies with cryptographic responsibilities. But there's been an enormous increase in public cryptographic work in the last quarter century, and in the accompanying controversies. This increase has been caused by the easy availability of computers and their interconnections (via the Internet and the web) and by the development of new ideas, such as public key cryptography, which allow for secure communication between parties who have made no previous commitment to each other. Every person who has used an ATM (automatic teller machine), made a 'phone call using a portable 'phone, or had their health records transmitted among caregivers or insurers should be concerned about secure communication. Social issues include the conflict between the right to privacy and the desire of some government agencies to have assured access to certain communications, and the difficulty and propriety of preserving intellectual property rights over a collection of bits.

Prerequisites The math background needed for this course is good knowledge of Algebra 2, and some knowledge of analytic geometry. We'll also need some acquaintance with graphing calculators, since we will write some simple programs on current graphing calculators which will help encrypt and decrypt messages. Knowing how to write such programs will not be needed. Some involvement with the web will be used. Such access is now easy at Rutgers due to the increasing presence of terminals on campus. Courses containing some material similar to what's below are now being given at non-specialized high schools, so the material is accessible to students having the mathematical preparation suggested here. We will certainly need to present the material carefully since our target student population will be those without technical majors or serious knowledge of mathematics.

Mathematical goals Students will learn about modular addition and finite fields. They will learn the basics of combinatorics such as various ways to count. Additional topics of discrete mathematics, including basic graph theory, may be studied. Appropriate topics from number theory (e.g., methods for factoring large numbers and alternative methods for exponentiating) will be explored. In addition, parts of probability (such as Bayes' Theorem) will be discussed. Depending on time and choice of topics, a bit of group theory may also be included. The question "What is an algorithm?" will be explored, along with descriptions of various cryptographic protocols. If time allows, there will be brief mention of the P versus NP question, which has been characterized as the fundamental problem in theoretical computer science. The mathematical topics will rarely be taught systematically, but will be supplied on a "just in time" basis ("infused into the curriculum") as some of the topics listed below need them. Traditional lecturing will be supplemented and, where possible, replaced by various active learning strategies. We hope to have writing assignments which will explore both social and mathematical issues.

Student interest and instructors The topics below are controversial and current and reach informally into the lives of students immediately (buying rock music over the Internet, sending "secret" messages between friends, ...). The topics are also intertwined with many serious public policy issues. Understanding the topics and the decisions related to them will be a part of 21^st century society. There's a great deal of current academic and industrial activity on cryptography and communications, and the number of people available to teach such a course at Rutgers is large. Interested and capable individuals abound in the Math and Computer Science Departments, and many are also found at DIMACS, an NSF-sponsored national center for discrete mathematics and theoretical computer science. There are many possible guest speakers for a course of this type working locally at such businesses as AT&T Research, Lucent, Bellcore, NEC, etc. Many of these industrial scientists have shown their abilities to speak at an appropriate level during the three week long summer meeting on Cryptography and Network Security (Dimacs Research and Education Institute, summer, 1997). Over 60 talks were given, most to an audience whose members had a quite varied mathematical background, ranging from high school teachers to academic researchers.

We present a list together with brief descriptions of topics which could be covered in a course of this nature. We currently plan to present this course for the first time during the fall '99 semester to a class of 20 to 30 students.

• A setting for cryptography
  Alice and Bob want to communicate. Eve will listen and try to decipher their communications. The generally accepted rules of the game are that Alice and Bob and Eve (the eavesdropper) all know what the communication methods are, but the Alice and Bob get to agree ahead of time on what specific ``key'' they will use. Eve is allowed to analyze the messages, and she will sometimes create messages and responses.
• What is information?
  During the late 1940's, Claude Shannon published a series of papers in the Bell System Technical Journal. He created a field now known as Information Theory. How much information can a stream of bits (0's and 1's) carry? How much information is there in a typical English language sentence? The redundancy in most natural languages frequently yields cryptographic weaknesses which can be exploited using simple probabilistic arguments. The basic concepts of information theory will be stated and explored.
• Randomness
  Electronic communication should look random if it conceals a message successfully. What does "random" mean, and how can pseudo-random data be constructed? The use of random bit streams to construct an unbreakable cryptosystem (the "one-time pad") will be mentioned, along with its practical problems. Discussion of these issues will involve material from several areas of mathematics and theoretical computer science.
• Sharing secrets
  How can two or more people share a secret? Suppose a company has a formula locked in a safe, and wants to have at least 3 people from a committee of 5 to agree whenever the safe is to be opened. What method can be used to guarantee this procedure? In 1979, Adi Shamir discovered an easy way to "share" such secrets. His method can be explained to anyone having knowledge of high school algebra and analytic geometry. It is used in many current computer protocols.
• Social issue #1: the security of e-mail
  The FBI asserts rather generally that secure cryptographic communication will be a great hindrance to capturing terrorists, criminals including drug traffickers, and spies. Therefore all information transmission should have "trapdoors" which the general population would allow the government access to, with suitable legal protection. Also, software sold internationally should have built-in limits to the kind of cryptographic protocols with which it can be easily linked. These assertions involve expensive hardware investments and severe restrictions on software. There is also doubt that the "key-escrow" schemes suggested by some government agencies can actually be managed in the real world. Should the U.S. government be allowed to prevent private parties from keeping secrets? Note that in some countries international travelers are not allowed to use any non-approved cryptographic communications devices.
• Social issue #2: the secrecy of medical records
  Some recent U.S. regulations essentially open all medical records to police agencies in order to decrease the chances of fraudulent medical billing. Other countries with complex health systems (such as Great Britain) have stringent protections built into medical records at many levels. Should "Aunt Agnes" know about your diseases and their treatments? Should a prospective employer be able to find out about any past treatment for emotional illness? What can be done practically to insure the security of medical records?
• Social issue #3: who should know how the money flows?
  There's evidence that some recently used European bank card systems are easily broken, and their vulnerabilities have been concealed because of the embarrassment of admitting the difficulties and the cost in resources and education of customers involved in replacing the systems. More generally, how secure should transaction systems be? And who should have access to information about financial transactions (e.g., if Alice buys pornography, who should know about it)?
• Social issue #4: what is the future of copyright in the digital world?
  Do I own my own writings or music or art, or does a reader or consumer of some type have other, sometimes conflicting rights? What about distributors? A large segment of society now makes money by trading these rights (e.g., the cost of physically producing a compact disc versus what it is sold for). Also see the discussion on digital watermarks for more about this.
• Auctions: secret bids in the open
  Suppose parties must submit a bid to an auction by a desired date, and the transactions may be vulnerable to a corrupt official, who may open a sealed bid to disclose information to competitors. Realistic cryptographic procedures can make detection of such cheating very likely.
• Timestamping without revealing
  How can one "timestamp" a document? For example, two parties may enter into a contract whose details they may prefer to keep private, but whose execution may reasonably be foreseen to involve the possibility of disagreement or even litigation. Techniques related to cryptography provide an opportunity to record the document publically in a condensed and secret fashion, with a very high likelihood that neither party can later deny the agreement or its details. These techniques are now in use.
• Digital watermarks
  The Internet is an interesting place for intellectual property. Images, sounds, and ideas, all with potentially high value, may be transported and copied easily. The protections which such systems as copyright and patent have afforded artists, composers, writers and inventors (and which have given large profits and power to distributors!) may be evaporating. How can the efficiencies of electronic distribution not compromise these historic rights? Many proposals have been made to embed ownership and transfer privileges "inside" these works, and to use that information to track misuse. The wonderful word "steganography" (meaning hidden writing) has been applied to the new field. This is a rapidly developing area because of its many important commercial applications. We'll try to follow the news.
• Precision in mathematical description
  What is a cryptographic protocol? What is an algorithm? We'll try to convey the idea of a comprehensive and coherent description of an algorithm. Several cryptographic protocols will be described precisely.
• A glance at history: Enigma
  Enigma was a German encryption system using before and during World War II. Solution of this system by a team of British mathematicians (one of whose members was Alan Turing) using techniques based on work done by Polish mathematicians was said to have helped Allied efforts substantially. Enigma will be described, and some idea of "how to solve it" will be given.
• A glance at current practice: DES
  DES, the Data Encryption Standard, is probably the single most widely used encryption method in the world. It is used in essentially every financial transaction handled by "wire", including those done with ATM's. A large amount of controversy accompanied the introduction of DES in the late 1970's. These controversies and the DES system will be described. DES is a rather complex block cipher system, and therefore similar but simpler "toy" systems will be studied.
• Public key systems
  The first "open" (non-classified) publication of a public key system was by Diffie and Hellman in 1976. Such methods allow Alice and Bob to communicate without having a mutually prearranged key, using only published information. The paradoxical aspect of such schemes is that their design allows privacy even though much of the system is available to everyone. The original proposal was shown to have some weaknesses but other suggestions were made, including RSA, published by Rivest, Shamir, and Adelman in 1978. RSA, Inc., is now an important company in secure electronic communication. Its systems and others (such as PGP) rely for their security directly on the presumed difficulty of such mathematical problems as factoring large numbers and finding "logarithms" in groups. Many confidential web transactions use RSA methods.
• Secret communication in the open
  Suppose Alice and Bob are in different prison cells, and Eve is the prison guard, transmitting all messages between Alice and Bob. Alice and Bob have no prearrangement for communication, nor have they access to any shared data. It is still possible, however, for Alice and Bob to have communication whose information will be secure from Eve with high probability. Peter Winkler, a mathematician working at Lucent Technologies, has used these ideas to develop legal bidding strategies in contract bridge which have been banned from formal play!
• Digital cash
  The money in your pocket is difficult to trace. As the world moves to a digital economy, bank transfers may become easier to trace resulting in a decrease of the privacy of financial transactions. Can "anonymous" forms of digital cash be created? What are the desired properties and problems of such cash?
• Coding theory
  Coding theory was created as a part of information theory. It contains a mathematical language which is also useful in cryptography. Coding theory studies how to send messages so that error-correction can be done efficiently while keeping information content high. The goal is to provide patterns for signaling so that if a message is distorted or damaged, the information it contains can be reconstructed.

Contributed by greenfie@math.rutgers.edu and last modified 10/11/98.