CMSC858K --- Spring 2007 --- Lecture Schedule

• [Jan 25: Lecture 1] Introduction, perfectly-secret encryption
  Introduction. Principles of modern cryptography. Defining and achieving perfect secrecy. Optimality of the one-time pad.
  
  
• [Jan 30: Lecture 2] Computational notions of security; pseudorandom generators
  An introduction to computational definitions of security. Pseudorandomness and pseudorandom generators. Private-key encryption beating the one-time pad.
  
  
• [Feb 1: Lecture 3] Private-key encryption
  Proof of security for the "pseudo"-one-time pad encryption scheme. Multi-message indistinguishability. Pseudorandom functions.
  
  
• [Feb 6: Lecture 4] Private-key encryption
  Proof of multi-message indistinguishability. The "birthday" bound. Pseudorandom permutations. Modes of encryption.
  
  
• [Feb 8: Lecture 5] Message authentication
  Message authentication codes and applications. Constructing secure MACs for fixed-length messages. From fixed-length MACs to arbitrary-length MACs. CBC-MAC.
  
  
• [Feb 13: Lecture 6] Collision-resistant hash functions
  CRHFs. Merkle-Damgard construction. Hash-and-MAC.
  
  
• [Feb 15: Lecture 7] Stronger security notions for private-key encryption
  Security against chosen-plaintext attacks, and security against chosen-ciphertext attacks. A construction achieving the latter.
  
  
• [Feb 20: Lecture 8] One-way functions and hard-core bits
  One-way functions, factoring as (giving rise to) a one-way function. Hard-core bits. The Goldreich-Levin theorem.
  
  
• [Feb 22: Lecture 9] Pseudorandom generators from one-way permutations
  Constructing a PRG from any one-way permutation. Increasing the expansion of a PRG.
  
  
• [Feb 27: Lecture 10] Pseudorandom functions from any pseudorandom generator
  Constructing a PRF from any length-doubling PRG. The Feistel/Luby-Rackoff construction of a pseudorandom permutation.
  
  
• [Mar 1: Lecture 11] Luby-Rackoff and on to number theory
  Finishing up the proof of 3-round Luby-Rackoff. Summary of where things stand thus far. Number theory.
  
  
• [Mar 6: Lecture 12] Some basic group theory and number theory
  Hardness of factoring (one view). Group theory. Generating random primes.
  
  
• [Mar 8: Lecture 13] Group theory and cryptographic hardness assumption
  The factoring assumption, the RSA assumption, and relations between the two. Cyclic groups and the discrete logarithm assumption.
  
  
• [Mar 13: Lecture 14] The Diffie-Hellman problems, and on to public-key cryptography
  The Diffie-Hellman assumptions. Public-key cryptography and the Diffie-Hellman key exchange protocol.
  
  
• [Mar 15: Midterm exam]
  
  
• [Mar 27: Lecture 15] Diffie-Hellman key exchange and public-key encryption
  Proof of security for Diffie-Hellman key exchange. Definitions of security for public-key encryption, and their equivalence. Textbook RSA and attacks.
  
  
• [Mar 29: Lecture 16] Public-key encryption I
  Padded RSA. Public-key encryption from trapdoor permutations, and achieving optimal ciphertext length. Hybrid encryption.
  
  
• [Apr 3: Lecture 16.5] Guest lecture by Bill Gasarch -- PIR
  
  
• [Apr 5: Lecture 17] Public-key encryption II
  El Gamal encryption. Introduction to Rabin encryption.
  
  
• [Apr 10: Lecture 18] Public-key encryption III
  A trapdoor permutation based on factoring. Rabin encryption.
  
  
• [Apr 12: Lecture 18] Digital signatures I
  Motivation for and functionality of digital signatures. Defining security.
  
  
• [Apr 17: Lecture 19] Digital signatures II
  Defining security. Insecurity of textbook RSA. Lamport's one-time signature scheme.
  
  
• [Apr 19: Lecture 20] The random oracle model I
  Introduction to the random oracle model. Pros and cons. Proofs of security in this model, and their meaning in practice.
  
  
• [Apr 24: Lecture 21] The random oracle model II
  Public-key encryption and digital signatures in the random oracle model.
  
  
• [Apr 26: Lecture 22] Public-key identification schemes
  Definitions of security for identification. "Deniability".
  
  
• [May 1: Lecture 23] Public-key identification schemes and zero knowledge
  Honest-verifier zero knowledge (HVZK) and applications to identification. HVZK proofs for all of NP.
  
  
• [May 3: Lecture 24] Zero knowledge I
  Witness indistinguishability (WI) and proofs of knowledge; applications to identification. Okamoto's WI proof of knowledge, and an identification scheme based on the discrete logarithm assumption.
  
  
• [May 8: Lecture 25] Zero knowledge II
  Zero knowledge against a cheating verifier. Commitment schemes based on one-way permutations and one-way functions. Zero knowledge proofs for all of NP.
  
  
• [May 10: Final exam]