The primary focus of this course will be on definitions and constructions of various cryptographic objects, such as pseudo-random generators, encryption schemes, digital signature schemes, message authentication codes, block ciphers, and others time permitting. We will try to understand what security properties are desirable in such objects, how to properly define these properties, and how to design objects that satisfy them.

Once we establish a good definition for a particular object, the emphasis will be on constructing examples that provably satisfy the definition. Thus, a main prerequisite of this course is mathematical maturity and a certain comfort level with proofs. I will be doing proofs in class, and you will be doing them on the homeworks.

Secondary topics that we will cover only briefly will be current cryptographic practice and the history of cryptography and cryptanalisys.

At the end of this course, you should be able to make sense of a good portion of current cryptography research papers and standards.

This course will not teach you how to make your computer secure. Cryptography is only one tool in computer security. The rest of computer security has to deal with such fascinating things as buggy code, poorly managed and ever-too-curious humans, the power consumption of smart cards, etc. We will mostly abstract all that away. I will, however, point out where the limitations of our models are and what else is needed for actual security.

This course will also not teach you how to implement the techniques we discuss in the most efficient manner. We will stop at cryptographic algorithms. The underlying number-theoretic algorithms will be discussed only briefly; the most advanced and efficient ones require more time than we will have. For example, if you only take this class, you should be able to program RSA, but many existing imlementations will be probably be much more efficient that yours.

Finally, this course will not teach you how to design the next great block cipher, such as DES or AES, or the next cryptographic hash function, such as SHA or MD5. (There are very interesting techniques people use for that, but, unfortunately, our current understanding of these techniques does not allow us to prove any security properties of the resulting constructions.) Nor will this course teach you how to ``break'' such designs.

Just because I will not teach these topics does not mean they are not worth your while. There are plenty of books and research papers to read and people to talk to if you are interested in pursuing any of these topics.

Below is a rather ambitious plan for the topics I intend to cover, roughly in order. We will probably have to omit some as we go along. If we have to omit anything, we'll try to omit the extra constructions and keep the definitions.

- Shannon's information-theoretic lowerbound and the Vernam cipher.
- One-way functions and one-way permutations. Examples (RSA,
Discrete Log, factoring).
- Hardcore bits. Goldreich-Levin construction.
- Pseudo-random generators (a.k.a. ``stream
ciphers''). Definitions. Blum-Micali construction. Blum-Blum-Shub
construction.
- The idea of public-key encryption. Trapdoor functions. RSA
(Rivest-Shamir-Adelman) and Rabin's schemes. Problem of defining
secure encryption.
- Definitions of secure encryption. Goldwasser-Micali
construction. Blum-Goldwasser construction.
- ElGamal encryption.
- Pseudorandom functions. Goldreich-Goldwasser-Micali construction.
- Pseudorandom permutations. Luby-Rackoff construction.
- Symmetric (non-public-key) encryption. Block ciphers and modes
of operation. DES, AES. Stream ciphers.
- Message authentication codes.
- Digital Signatures. Rabin and RSA constructions. Problem of
defining secure signatures.
- Definition of secure signatures. Goldwasser-Micali-Rivest
construction. Cramer-Shoup construction.
- Collision-Resistant Hash Functions. Examples.
- Random oracle model. Bellare-Rogaway signature schemes.
Fiat-Shamir methodology.
- Back to encryption: adversary malicious and interactive.
Resulting problems and new definitions. OAEP construction.
Cramer-Shoup encryption scheme.
- A taste of more advanced topics (identification schemes, secret sharing, commitment schemes, zero-knowledge,...)