Description of the proposed Rutgers mathematics course:
The Mathematics of Communications: keeping secrets
Three may keep a secret, if two of them are dead.
Benjamin Franklin
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
nonspecialized 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 NSFsponsored 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.
Some possible topics
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 pseudorandom
data be constructed? The use of random bit streams to construct an
unbreakable cryptosystem (the "onetime 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 email
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 builtin
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
"keyescrow" 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
nonapproved 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" (nonclassified) 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 errorcorrection 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.