## Lecture Summaries

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

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/6/2006) (.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. Definitions.
Read: [GB notes, chap. 1, sec. 6.3-6.4, 2.1-2.2].

• Lecture 2 (9/13/2006) (.pdf). One-way functions, permutations and trapdoor permutations. Applications: UNIX password authentication, S/Key one-time password system. Problems with using (iterated) one-way (trapdoor) permutations for both puclic- and private-key ecnryption. Examples of one-way functions: RSA, Modular Exponentiation, Integer Multiplication, Modular Squaring. Main problems and criticism of one-way functions: reveal partial information, not ``pseudorandom''.
Read: [GB notes, sec. 2.3, 7.2].

• Lecture 3 (9/20/2006) (.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: refresh number theory (handouts in class, skim appendix C in [GB notes]).

• Lecture 4 (9/27/2006) (.pdf). Motivation to hardcore bits. Examples: MSB for discrete log, LSB for squaring. Definition. General construction (Goldreich-Levin). 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: [GB notes, sec. 2.4, 3.0-3.2].

• Lecture 5 (10/4/2006) (.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: [GB notes, sec. 3.3-3.4].

• Lecture 6 (10/11/2006) (.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. Semantic security and its equivalence to CPA indistinguishability.
Read: [GB notes, sec. 7-7.4.5].

• Lecture 7 (10/18/2006) (.pdf). 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. Symmetric-Key Encryption. One-time definition and scheme. CPA definition and closure under composition.
Read: [GB notes, sec. 10.1, 6.1, 6.3, 6.5].

• Lecture 8 (10/25/2006) (.pdf). 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: [GB notes, 6.1, 6.3, 6.5-6.7, 6.12.2, 5-5.3].

• Lecture 9 (11/01/2006) (.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: [GB notes, sec. 4.4, 5-5.4, 5.6, 5.9-5.12, 6.2, 6.8-6.9, 6.12.1]

• Lecture 10 (11/08/2006) (.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: [GB notes, sec. 5.4, 5.6.2, 5.10, 4-4.4, 6.2, 6.8-6.9, 8-8.5]

• Lecture 11 (11/15/2006) (.pdf). Examples of UHFs: information-theoretic examples, XOR-MAC, CBC-MAC, HMAC. Another XOR-MAC and e-xor-universal hash functions. Variable-length messages.
Read: [GB notes, chap. 8]

• Lecture 12 (11/29/2006) (.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).
Read: [GB notes, sec. 9-9.3]