Cryptography allows us to achieve secure and private communication over insecure channels. When used improperly, however, it can result in stolen credit card numbers, leakage of embarrassing secrets, impersonations, and so on. The objective of this course is to understand the foundations that allow the secure building of cryptosystems, with an emphasis on rigorous definitions and proofs of security and a critical eye towards the assumptions that allow us to achieve various forms of cryptography. If time permits we will also touch on some more recent topics like fully homomorphic encryption and database privacy.
This is a tentative schedule of the lectures. Changes are possible depending on progress and interest.
||What is cryptography? The one-time pad. Computational assumptions.||[pdf]|
||Message indistinguishability and semantic security. Pseudorandom generators. Private-key encryption.||[pdf]|
||Chosen plaintext attacks and pseudorandom functions.||[pdf]|
||Construction of pseudorandom functions. Message authentication. Chosen ciphertext attacks.||[pdf]|
||Construction of CCA-secure encryptions. Variable-length MACs.||[pdf]|
||Cryptographic hash functions. One-way functions and pseudorandom generators.||[pdf]|
||The Goldreich-Levin theorem.||[pdf]|
||Public-key encryption from trapdoor permutations. Trapdoor permutatons based on hardness of factoring.|
||Digital signature schemes.||[pdf]|
||Database privacy: Definitions and the Laplace mechanism.||[pdf]|
||Database privacy: Sanitization and the Blum-Ligett-Roth mechanism.|
|Dec 12||Project presentations in ELB 304|
Notes will be provided for every lecture. A substantial part of the course will closely follow the topics in the first book. The second and third books are great references for the theory of cryptography and cover much of the remaining material.
Here are some notes on probability that refresh some basic concepts and explain the notation we use.