DREI'97 Summer Course:

Cryptography

Discrete Mathematics

Course Instructor

Steven Rudich is an Associate Professor of Computer Science at Carnegie Mellon University. His research interests are in computational complexity theory and the mathematical foundations of cryptography. You can find out more about him from his web page:

www.cs.cmu.edu/~rudich

JAVA Applets

Course Overview

This course contains ten lectures that develop the basic ideas behind modern cryptography and five lectures on special topics in discrete mathematics. The lectures are specially chosen to contain material that will transfer easily to the high school classroom. The special topics are chosen because they have been particularly well received by high school audiences.

Syllabus

Lecture 1. All About Alice, Bob, and Eve
Introduction to the problem of private communication over a public channel. The basic formal paradigm. Code making versus code breaking. An unbreakable code and perfect secrecy.

Lecture 2. Pancakes With a Problem
Sorting stacks of pancakes by reversing the top portion with a spatula. The notion of an algorithm. Counting the number of flips required to sort a stack of n pancakes. Upper and lower bounds on the pancake numbers. Inspiration versus perspiration.

Lecture 3. Raising to Powers
What is the fastest way to raise a number to an integer power by repeated multiplication of previously obtained results? Upper and lower bounds. Repeated squaring method.

Lecture 4. Grade School Revisited: How To Multiply Two Numbers
How fast can we multiply two numbers? Big O notation and growth rates. Improving on the traditional method. Recurrence relations.

Lecture 5. How To Count Without Counting
Elementary principles for counting large sets without enumerating them. The Correspondence Principle and the Multiplication Principle. Checking for mistakes using the Sleuth's Criterion. Counting Poker hands.

Lecture 6. A Fundamental Mathematical Abstraction: Groups
Basic group theory Z*n. Lagrange's Theorem.

Lecture 7. Betting on the Computational Limitations of the Adversary
What is the nature of cryptography when the message is longer than the key? The RSA cryptosystem. the Diffie-Hellman cryptosystem. Public-key versus private-key cryptography.

Lecture 8. Who Has the Advantage in Traditional Dating?
The problem of finding a stable pairing among n boys and n girls given arbitrary preference lists for each individual. The traditional marriage algorithm. The naked mathematical truth about which sex has the upper hand in traditional dating.

Lecture 9. Factoring
The history and apparent difficulty of factoring a number into primes. Factoring algorithms.

Lecture 10. Quadratic Residues and Factoring
Taking square roots modulo an integer is as hard as factoring it. Blum integers. The repeated squaring generator and pseudorandomness.

Lecture 11. The Science of Modern Cryptography
Putting the pieces together. Private-key cryptography and one-way functions. Public-key cryptography and trapdoor-functions. The possibility of unbreakable codes based on the computational hardness of problems.

Lecture 12. Machines That Can't Count
The simplest interesting computers: Finite Automata. A visual programming language that you can learn in five minutes. Cool programs. Inherent limitations of these machines. Cellular automata and the firing squad problem.

Lecture 13. Flirting With Infinity
How to compare infinite sets. Different orders of infinity. Cardinal numbers.

Lecture 14. Sharing Secrets With Polynomials
Finite fields. Counting the number of polynomials of degree d that pass through a given number of points. Shamir's secret sharing scheme. Application to nuclear missle launching.

Lecture 15. Magical Protocols
How to compute the average salary of a group of people without anyone revealing any information about his/her salary. Zero-knowledge. Other surprises...