Lecture Summaries

The descriptions below will summarize what we did up to now and will give the plan for the upcoming lecture. It might also suggest optional reading for each lecture.

• Lecture 1 (9/4/2002). Problem of secret communication. ``Classical'' schemes and attacks on these schemes. One-time pad and Shannon's definition of perfect security.

• Lecture 2 (9/9/2002). Shannon's impossibility result and limitations of perfect security. Modern Cryptography: computationally bounded adversaries. One-way function and permutations: motivation and formal definitions.

• Lecture 3 (9/11/2002). Applications: UNIX password authentication, S/Key multi-time password system. First proof by a reduction.

• Lecture 4 (9/16/2002). Cryptographic proof methodology and logic:
Intuition->Definition->Scheme under some assumption->Proof of security by reduction->DONE!
Cryptographic reductions in more detail. How to prove some statement is generically true or false. Problems with OWFs/OWPs: (a) random inputs, (b) only way to invert is to ``know'' the input (leads to trapdoor permutations); (c) reveal partial information (leads to hardcore bits).
Also see Cryptography Methodology (by Bellare and Rogaway).

• Lecture 5 (9/18/2002). Public- vs. Secret-key cryptography. Trapdoor Permutations. Problems with using iterated one-way/trapdoor permutations. Motivation to hardcore bits. Definition and general construction (Goldreich-Levin).

• Lecture 6 (9/23/2002). Guest lecture: introduction to computational number theory. Facts about arithmetic modulo a prime, and modulo composite.
Reference: Number theory primer (.pdf).

• Lecture 7 (9/25/2002). Guest lecture: computational number theory. More facts about arithmetic modulo a prime and composite. Various OWFs/OWPs/TDPs including modulo exponentiation, squaring.
Reference: Number theory primer (.pdf).

• Lecture 8 (9/30/2002). Chinese remaindering and its applications. RSA. Hardcore bits for discrete log, squaring and RSA.
Reference: Number theory primer (.pdf).

• Lecture 9 (10/2/2002). Saving one bit: building ``secure'' encryption from OWPs and hardcore bits. Saving more bits using iterated OWPs. Pseudorandom one-time pads and motivation to pseudorandom generators (PRGs). Formal definition. General notion of computational indistinguishability.

• Lecture 10 (10/7/2002). Computational Indistinguishability and hybrid argument. Properties of PRGs (e.g., closure under composition, stretching PRG's by any polynomial amount). Next-bit test and its equivalence to PRGs. Proof that iterated OWP construction is a PRG.

• Lecture 11 (10/9/2002). Equivalence of PRG's to OWF's. Definition of secure one-time encryption, construction from PRGs. One-time pad lemma. Encrypting unbounded number of bits: stream ciphers.

• Lecture 12 (10/14/2002). Forward Security. Constructions of (forward-secure) stream ciphers. (a) general - iterated PRGs; (b) special case of (a) - iterated OWP; (c) special case of (b) - BBS generator and its special properties; (d) practice - example of RC4. Stream Ciphers => stateful secret-key encryption. Stateless encryption of multiple messages? Motivation for pseudorandom functions (PRFs).

• Lecture 13 (10/16/2002). Definition of PRFs. Construction from PRGs and equivalence to OWFs. Expanding output of a PRF. Random Function methodology. Application: simple identification scheme (friend-and-foe).

• Lecture 14 (10/21/2002). Applications of PRFs to secret-key encryption: CTR and XOR schemes, their comparison, discussion of ``nonces''. Birthday attack. Definition of multiple-use encryption and of chosen plaintext attack (CPA). Randomization vs. State. Practice: block ciphers. Stream vs. Block Ciphers. Modeling block ciphers as pseudorandom permutations (PRPs). PRPs vs. PRFs.

• Lecture 15 (10/23/2002). Luby-Rackoff construction and Feistel network. Real life block ciphers (AES, DES). Strong PRPs. Block ciphers and their modes of operation. ECB, CTR, randomized CTR modes and their proof of security.

• Lecture 16 (10/28/2002). More modes: CFB, OFB, CBC modes and proof of their CPA-security. Importance of avoiding ``collisions''. Exact security and its importance. Introduction to message authentication.

• Lecture 17 (10/30/2002). Message authentication schemes. Difference between privacy and authenticity. Sending message in the clear -- message authentication codes (MACs). PRF is a MAC. Equivalence between MACs, PRFs, PRPs, OWFs. MACs as unpredictable functions. Extending the domain of a MAC/PRF: ``block-by-block'' approach (tricky/inefficient) and ``hash functions'' approach. epsilon-universal hash functions and collision-resistant hash functions. Main composition theorem: PRF(H(m)) is a PRF.

• Lecture 18 (11/4/2002). Examples of MACs following the composition theorem: information-theoretic, CBC-MAC, XOR-MAC-1. Another approach (f_s(nonce) + H_u(m)), and another XOR-MAC-2.

• Lecture 19 (11/6/2002). Putting pieces together: authenticated encryption (AE). Implication to chosen ciphertext attack (CCA). Examples of AE schemes (encrypt-then-mac, ad-hoc, prp-based).

• Lecture 20 (11/11/2002). From ``short'' to ``long'' authenticated encryption: special integrity-aware modes (OCB,IAPM,IACBC), using generic constructions + known tools for basic primitives, using ``concealment''. Construction of concealment using CRHFs. Application to remotely-keyed authenticated encryption.

• Lecture 21 (11/13/2002). Collision-resistant hash functions (CRHFs). Ideal Cipher construction (similar to ``real-life''; e.g. SHA1, MD5). Composition of CRHF's, Merkle-Damgard Construction, Merkle trees.

• Lecture 22 (11/18/2002). Back to Number theory. CRHF construction based on Discrete Log. Introduction to Public-key cryptography. Model, key distribution savings. Revisiting encryption and authentication. Public-Key encryption and the basic tool -- TDPs. Insecurity of deterministic ``trapdoor permutation'' schemes like RSA. IND-CPA definition. Malleability and IND-CCA definition.

• Lecture 23 (11/20/2002). One-bit IND-CPA secure scheme from hardcore bits (Blum-Goldwasser): (f(r),h(r)+b). Encrypting many bits: generic bit-by-bit composition, more efficient construction from iterated hardcore bits. Random oracle model, and nearly optimal construction in this setting: (f(r), H(r)+m).

• Lecture 24 (11/25/2002). More general ways to encrypt many bits: key encapsulation (works for both CPA and CCA). Special cases: hybrid encryption, examples from previous lecture. IND-CCA-secure scheme in the random oracle model: (f(r), E_H(r)(m)).

• Lecture 25 (11/27/2002). Key encapsulation from particular number theoretic assumptions. DDH assumption and Diffie-Hellman Key exchange. ElGamal CPA-secure encryption. Cramer-Shoup CCA-secure key encapsulation and encryption. ``Direct'' CCA-encryption in the random oracle model. OAEP padding and its variants.

• Lecture 26 (12/2/2002). Public-key authentication: digital signatures. Definitions, RSA and Rabin's signatures. Trapdoor approach and its deficiency. Signature paradox and its resolution. Hash-then-sign paradigm. Practical hash-then-sign in the random oracle model: full domain hash. Exact security and improvements to FDH for ``homomorphic'' trapdoor permutations (RSA-FDH, RSA-PFDH, RSA-PSS).

• Lecture 27 (12/4/2002). Towards signatures in the standard model: one-time signatures. Lamport Scheme. Merkle signatures and bottom-up hash trees. Applications of Merkle tree to compression/commitment with logarithmic proof of validity. Naor-Yung construction and top-down authentication trees. Application to public-key certification: certificate chains. A glimpse at practical signatures w/o random oracles.

• Lecture 28 (12/9/2002). Identification Schemes. Brief definitions (key-only, passive, active), several constructions (from signature and encryption; works for both public- and symmetric key). Identification from proofs of knowledge. Proving knowledge of discrete log and RSA: Schnorr and GQ protocols. Fiat-Shamir heuristic for building signature schemes: passive ID <=> CMA-secure signature. Schnorr and GQ signatures.

• What's next? (never happened). Many things we did NOT cover... Commitment Schemes. Zero-knowledge. More Identification protocols, RO model (incl. OAEP and Fiat-Shamir heuristics), CCA and non-malleability, authenticated encryption, key exchange. Oblivious transfer and PIR, secret sharing and VSS, threshold crypto, multiparty computation and SFE (incl. coin-flipping), gadgets (trapdoor commitments, deniable encryption, blind signatures, etc.)... Cryptanalysis (incl. applications of lattices), e-commerce, anonymity (incl. pseudonyms, mix-nets), electronic voting, key exposure (incl. forward and key insulated security), broadcast encryption/traitor tracing...