Summary
The modern study of cryptography investigates techniques for facilitating interactions between distrustful entities. In our connected society, such techniques have become indispensable--- enabling, for instance, automated teller machines, secure wireless networks, internet banking, satellite radio/television and more. In this course we introduce some of the fundamental concepts of this study. Emphasis will be placed on rigorous proofs of security based on precise definitions and assumptions.
Topics include: one-way functions, encryption, signatures, pseudo-random number generation, zero-knowledge and basic protocols.
Note: This will be a theory course. You will be expected to read and write formal definitions and mathematical proofs. This is not a course in security: you will not learn how to secure your system. Cryptography is only one (important) part of security. We will not study cryptographic acronyms or all cryptographic protocols in use today. Rather we focus on some of the fundamental design paradigms and on notions that will allow you to critically evaluate cryptographic protocols.
Topics Outline (Subject to Change)
- Introduction [Lectures Notes (pdf)] [KL 1,2]
- W 08.29 Introduction & Overview
- F 08.31 Information Theoretic Security
Shannon's Definition of security. One-time Pads. Limitations of the Information Theoretic Approach.
- Computational Hardness and One-wayness [Lecture Notes (pdf)][KL 3.1,7]
- W 09.05 One-way Functions and Computationally bounded adversaries.
Randomized Efficient Algorithms. One-way functions (OWF). Weak and Strong OWFs.
- F 09.07 Computational
Number Theory.
Collections of OWFs.Euclid's Algorithm, Modular Exponentiation, Basic group theory, Euler's and Fermat's Theorems, Primes.
- W 09.12 Computational Hardness.
Factoring assumption and the Discrete log assumptions. One way permutation and Trapdoor permutations.
- F 09.14 Collections of OWFs.
- Indistinguishability and Psuedo-Randomness [Lecture Notes (pdf)]
- W 09.19 Computational Indistinguishability
Indistinguishability
- F 09.21 Indistinguishability, Hybrid Lemma, Pseudo-randomness
- W 09.26 Next-bit Test, Pseudo-random generators
- F 09.28 Pseudo-random generators
Constructions based on permutations and hard-core bits, Example construction based on discrete log
- W 10.03 Pseudo-random generators & Functions
One-bit expansion to Many-bit expansion constructions, definitions of pseudo-random functions
- F 10.05 PRFs and Private-key Encryption
Construction of a PRF, applications to encryption
- W 10.10 Private-key Encryption
Many-message Encryption, CPA, CCA Encryption
- F 10.12 Midterm
- W 10.17 CCA1/2-secure Private-key Encryption
- F 10.19 Public-key Encryption
General constructions from permutations and hard-core bits
- W 10.24 Public-key Encryption
El Gamal
- Knowledge [L19,L20]
- F 10.26 Interactive Proofs
Examples of Waldo, Graph Isomorphism
- W 10.31 Interactive Proofs + Zero-Knowledge
Definition, construction for Graph-Isomorphism
- F 11.01 Zero-knowledge
Definition, 3-coloring protocol for NP languages
- W 11.06 Commitments
- Semantical Security
Knowledge-based definitions of encryption. Equivalence with indistinguishability-based definitions.
- F 10.26 Interactive Proofs
- Authentication [Lecture Notes]
- Digital Signatures
Definitions and Constructions
- Hash functions
- Message Authentication Codes
- Zero-Knowledge based Authentication
- Computing on Secret Inputs [L26]
- Secret Sharing
- Secure Computation
Oblivious Transfer.
General secure computation.
Suggested Reading
Lecture notes will be made available; but should not serve as a substitute for the lectures. In particular, lecture notes might sometimes be posted after the class.
There is no required text for the course other than the lecture notes. You may find the following two books to be useful references. Note, however, that we will not always be following the same notational conventions as these books.
- Jonathan Katz and Yehuda Lindell. An Introduction to Modern Cryptography. This is a introductory textbook on cryptography. The level of the material and the mathematical treatment is similar to the one we will use in class.
- Oded Goldreich. Foundations of Cryptography. This is a very comprehensive treatment of the theoretical foundations of cryptography. Volume I and II include most of the material that we cover in class, but at a far greater depth and at a more advanced level. This book is a great reference for students interested in more advanced studies in theoretical cryptography.
For a more applied treatment of cryptography, I suggest the following book which is available on-line.
- Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography.
For background reading on probability, algorithms, and complexity theory, I recommend:
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms
- Michael Sipser. Introduction to the Theory of Computation.
Grading
There will be 5 homeworks, a mid-term and a final exam. The midterm is in class on Oct 10. Weights: homeworks 60%, mid-term 15% and final 25%.
Homework Policy
You are free to collaborate with other students on the homework, but you must turn in your own individually written solution and you must specify the names of your collaborators. Additionally, you may make use of published material, provided that you acknowledge all sources used. Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to a member of the course staff.
Assignments will be posted on this website. Typed problem sets are strongly preferred. I recommend that you learn and use LaTeX. Homework need to be handed in before the beginning of class. Additionally, you have a total of 4 "late-days" that you can use throughout the semester.