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, commitment schemes 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.

In addition to proofs, we will also study many practical
cryptosystems, such as RSA, ElGamal, Diffie-Hellman, DES, RC4, SHA-1
and so on. However, instead of simply taking these acronyms as a
black-box, we will see precisely how they are built, and what security
level they achieve in various scenarios. ** No programming will be
required for this course.**

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.

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. Universal Hash Functions.
Hash-then-authenticate method.
- 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. Merkle-Damgard
Construction. 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.
- Commitment Schemes.
- A taste of more advanced topics (identification schemes, secret sharing, zero-knowledge,...)