This class teaches the theory, foundations and applications of modern cryptography. In particular, we treat cryptography from a complexity-theoretic viewpoint. In recent years, researchers have found many practical applications for these theoretical results, and so we will also discuss their impact along the way and how one may use the theory to design secure systems.
Official Course Description
CS276: Cryptography. Prerequisite: CS170. Graduate survey of modern topics on theory, foundations, and applications of modern cryptography. One-way functions; pseudorandomness; encryption; authentication; public-key cryptosystems; notions of security. May also cover zero-knowledge proofs, multi-party cryptographic protocols, practical applications, and/or other topics, as time permits.
This list is tentative and subject to change.
- Introduction. Basic motivating scenarios for cryptography. History. Information-theoretic secrecy.
- Block ciphers. Standard modes of operation.
- Pseudorandom functions. Pseudorandom permutations. The birthday paradox. Applications. One-way functions.
- Symmetric encryption schemes. Definitions. IND-CPA. Security of standard modes of operation. IND-CCA2.
- Message authentication. MACs. Definitions. PRFs as MACs. CBC-MAC.
- Authenticated encryption. INT-PTXT. INT-CTXT. Non-malleability.
- Commitment schemes. Hard-core predicates. Goldreich-Levin theorem.
- Pseudorandom generators. PRG’s from OWF’s. Blum-Micali-Yao.
- PRF’s from PRG’s. Goldreich-Goldwasser-Micali
- Basics on number theory. Number-theoretic primitives. RSA. Rabin’s function. Definition of trapdoor one-way functions.
- Public-key encryption. Definitions. Semantic security. Message indistinguishability. Goldwasser-Micali cryptosystem. Hybrid encryption.
- Digital signatures. Trapdoor signatures. RSA. Random oracles. Full-domain hash. PSS.
- Zero knowledge proofs. Proofs of knowledge.
- Foundations. Constructions of signatures based on any one-way function. Oracles and separations.
If there is time, advanced topics may also include:
- Secret sharing. Shamir’s scheme. Generalized access structures.
- Threshold cryptography. Verifiable secret sharing. Proactive security.
- Secure voting schemes. Electronic cash.
- Secure multi-party computation.
- Cryptographic protocols.