Lecture Summaries (Fall 2008)

The descriptions below will briefly summarize what we did up to now and will give the plan for the upcoming lecture. The link for each lecture will also give more detailed (.ps or .pdf) lecture notes for the corresponding lecture. These lecture notes are heavily based on the

Lecture Notes for Fall 2006 class

Therefore, if you want to see what we will cover next, I recommend you consult the above notes. Sometimes, at the end of the summary I might suggest additional (optional) reading for each lecture. Make sure you also check the Handouts section for other handouts.

• Lecture 1 (9/2/2008) (.pdf). Problem of secret communication. One-time pad and Shannon impossibility result. Modern Cryptography: computationally bounded adversaries. Private-Key vs. Public-Key Cryptography. In search of public-key solution: motivation for one-way functions and trapdoor permutations.
  Read: [Katz-Lindell, chap. 1,2], [Boneh-Shoup, sec 2.1,2.2]

• Lecture 2 (9/9/2008) (.pdf). One-way functions and permutations. Collections of OWFs/OWPs. (Conjectured) examples of one-way functions: Integer Multiplication, Modular Exponentiation. Applications: UNIX password authentication, S/Key one-time password system. Cryptographic assumptions and proof by reduction. Formal security proof for S/Key.
  Read: [Katz-Lindell, sec 3.1, 6.1.1-6.1.2, 7.4.1] [Boneh-Shoup, 10.1-10.4].

• Lecture 3 (9/16/2008) (.pdf). Brish-up on number theory. Primes vs. composites, easy and hard problems. RSA, discrete log, factoring, square root extraction. Chinese remainder theorem. Examples.
  Read: see number-theoretic handouts in the Handouts section, [Katz-Lindell, sec. 7].

• Lecture 4 (9/23/2008) (.pdf). Trapdoor permutations. Toy PKE. Main problems and criticism of one-way functions: reveal partial information, not ``pseudorandom''. Motivation to hardcore bits. Examples: MSB for discrete log, LSB for squaring. Definition. General construction (Goldreich-Levin). [maybe: Relation to list-decodable codes.] Getting more bits out: construction based on hardcore bits of one-way permutations. Informal Applications to public- and secret-ket encryption. Definitions of pseudorandom generators. Definition of next-bit test.
  Read: [Katz-Lindell, 6.1.3, 6.3, 3.3, 3.4.1], [Boneh-Shoup, 21.2].

• Lecture 5 (9/30/2008) (.pdf). Proving the general construction satisfies the next-bit test. Showing that next-bit test implies all statistical tests. Computational Indistinguishability and its properties, hybrid argument and its importance. PRG Examples: Blum-Micali, Blum-Blum-Shub. Properties of PRG's (e.g., closure under composition). Equivalence to OWF's. Forward-Secure PRG's: generic construction is forward-secure, builing forward-secure PRG from any PRG, application to secret-key encryption.
  Read: [Katz-Lindell, 3.3, 3.4.1, 6.4], [Boneh-Shoup, 3.1, 3.4-3.5]

• Lecture 6 (10/7/2008) .pdf). Public-Key encryption. Problems with TDP approach and deterministic encryption in general. Encrypting single bits, definition of indistinguishability. Scheme based on TDP's. Extending to many bits: PK-only definition. Blum-Goldwasser scheme and formal proof of security (using PRG's). Key Encapsulation mechanisms (KEMs). General one-bit => many bits construction. General indistinguishability under CPA attack.
  Read: [Katz-Lindell, 10.1, 10.2, 10.4, 10.7], [Boneh-Shoup, 10.1-10.4, 11.1-11.3]

• Lecture 7 (10/14/2008) (.pdf). Semantic security and its equivalence to CPA indistinguishability. General GL transformation from OW to CPA secuirty. Diffie-Hellman Key Exchange. ElGamal Key Encapsulation and Encryption Scheme. CDH and DDH assumptions. Security of ElGamal under CHD and DDH. Other PK encryption schemes.
  Read: [Katz-Lindell, 3.2.2, 10.5, 10.7, 9.3, 9.4], [Boneh-Shoup, 10.5-10.6, 11.4-11.5]

• Lecture 8 (10/21/2008) (.pdf). Symmetric-Key Encryption. One-time definition and scheme. CPA definition and closure under composition. Stateful schemes (stream ciphers) based on forward-secure PRGs. Towards stateless schemes: pseudorandom functions (PRFs). Definition, construction using PRGs, Naor-Reingold construction using DDH.
  Read: [Katz-Lindell, 3.2-3.4, 6.5], [Boneh-Shoup, 3.1-3.3, 4.4., 4.6, 5.1-5.3]

• Lecture 9 (10/28/2008) (.pdf). Applications of PRFs: friend-and-foe, secret-key encryption. CTR and XOR schemes, their comparison. Pseudorandom permutations (PRPs). PRPs vs. PRFs. Luby-Rackoff construction using the Feistel network. Strong PRPs. Block ciphers and their modes of operation: ECB, CTR, CFB, OFB, XOR, CBC.
  Read: [Katz-Lindell, 3.5-3.6, 6.6], [Boneh-Shoup, 4.1, 4.3, 4.5, 5.2-5.4]

• Lecture 10 (11/04/2008) (.pdf). CPA-security of CFB,OFB,CBC modes. Exact security and its importance. Practical ciphers: DES, AES. Integration of symmetric and asymmetric encryption schemes. The problem of authentication. Message authentication codes (MACs). Definition of security: existential unforgeability against chosen message attack. Construction using PRFs. Unpredictable functions, their relation to MACs and PRFs. Reducing MAC length: using e-universal hash functions (e-UHFs).
  Read: [Katz-Lindell, 3.6, 4.1-4.4], [Boneh-Shoup, 5.4, 6.1-6.2, 7.1, 7.3]

• Lecture 11 (11/11/2008) (.pdf). Examples of UHFs: information-theoretic examples, XOR-MAC, CBC-MAC, HMAC. Another XOR-MAC and e-xor-universal hash functions. Variable-length messages. CCA security for symmetric encryption. Example PRP(m|r). Authenticated encryption. AE implies CCA security. Encrypt-then-MAC method. More advanced methods.
  Read: [Katz-Lindell, 4.5, 4.7-4.9, 3.7], [Boneh-Shoup, 7.2-7.5, 6.3-6.6, 6.10, 8.7, 9.1-9.3]

• Lecture 12 (11/18/2008) (.pdf). Collision-Resistant Hash Functions (CRHFs). Merkle-Damgard domain extender. Merkle trees and applications. Davied-Meyer's construction in the Ideal-Cipher Model. Claw-Free Permutation (CFP) Pairs. Examples from RSA, discrete log and squaring. CRHFs from CFPs. CRHFs imply OWFs but not conversely. Optimizing the construction using Discrete Log (homework for RSA). Digital signatures. Definition: attack (CMA), goal (existential unforgeability). Hash-then-sign paradigm.
  Read: [Katz-Lindell, 4.6, 12.1-12.4], [Boneh-Shoup, 8.1-8.5, 10.8, 13.1-13.2]

• Lecture 13 (11/25/2008) (.pdf). Moving to public-key: digital signatures. Definitions, RSA and Rabin's signatures. Trapdoor approach and its deficiency. Signature paradox and its resolution. Towards better signatures: one-time signatures. Lamport Scheme. Merkle signatures. Naor-Yung construction. Random oracle model and practical hash-then-sign signatures: full domain hash. Practical signature without random oracles: Cramer-Shoup scheme (mention).
  Read: [Katz-Lindell, 12.5-12.6, 12.8, 13.1, 13.3], [Boneh-Shoup, 13.3-13.4, 14.1-14.5]

• Lecture 14 (12/2/2008) (.pdf). Commitment Schemes. Definition and properties. Increasing input size: bit-by-bit composition, hash-then-commit technique using CRHF's. Constructions: from (1) OWF's, (2) OWP's, (3) CRHF's and (4) Pedersen commitment (based on DL). Relaxed commitments and composition using UOWHF's. Applications: bidding, coin-flipping, parallel authenticated encryption, password authentication, zero-knowledge.

Last modified: January 25, 2012