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.

. Problem of secret communication. ``Classical'' schemes and attacks on these schemes. One-time pad and Shannon's definition of perfect security.**Lecture 1 (9/4/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 2 (9/9/2002)**. Applications: UNIX password authentication, S/Key multi-time password system. First proof by a**Lecture 3 (9/11/2002)***reduction*.. Cryptographic proof**Lecture 4 (9/16/2002)***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).. 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 5 (9/18/2002)**. Guest lecture: introduction to computational number theory. Facts about arithmetic modulo a prime, and modulo composite.**Lecture 6 (9/23/2002)**

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

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

Reference: Number theory primer (.pdf).. 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**Lecture 9 (10/2/2002)***computational indistinguishability*.. 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 10 (10/7/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 11 (10/9/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.**Lecture 12 (10/14/2002)***Stateless*encryption of multiple messages? Motivation for pseudorandom functions (PRFs).. 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 13 (10/16/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 14 (10/21/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 15 (10/23/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 16 (10/28/2002)**. Message authentication schemes. Difference between privacy and authenticity. Sending message in the clear -- message authentication**Lecture 17 (10/30/2002)***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.. 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 18 (11/4/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 19 (11/6/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 20 (11/11/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 21 (11/13/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 22 (11/18/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 23 (11/20/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 24 (11/25/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 25 (11/27/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 26 (12/2/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 27 (12/4/2002)**. Identification Schemes. Brief definitions (key-only, passive, active), several constructions (from signature and encryption; works for both public- and symmetric key). Identification from**Lecture 28 (12/9/2002)***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...