Lecture Summaries

The descriptions below will summarize what we did up to now and will give the plan for the upcoming lecture. It will also suggest optional reading for each lecture. Sometimes this reading will include more information than what we covered (and than you probably need to know). Some of this information should indeed be skipped (it is too deep for our introductory course), while some other will contain the proofs and discussion that is useful, but was not done in class due to the lack of time. You should use your intellegence to skip the ``unclear (advanced) parts'' and extract the useful information. Do not worry, it is usually very easy to do.

• Lecture 1 (9/6/2001). 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: this web page, [GB notes, chap. 1, sec. 6.3-6.4, 2.1-2.2].

• Lecture 2 (9/20/2001). Examples of one-way functions: RSA, Modular Exponentiation, Integer Multiplication, Modular Squaring. 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. Main problems and criticism of one-way functions: reveal partial information, not ``pseudorandom''.
  Read: [GB notes, sec. 2.3, 7.2].

• Lecture 3 (9/21/2001). Brish-up on number theory. Primes vs. composites, easy and hard problems. RSA, discrete log, factoring, square root extraction. Chinese remainder theorem. Primality tests.
  Read: refresh number theory (handouts in class, skim appendix C in [GB notes]).

• Lecture 4 (9/27/2001). Motivation to hardcore bits. Examples: MSB for discrete log, LSB for squaring. Definition. General construction (Goldreich-Levin). 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/2001). 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/2001). 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). General one-bit => many bits construction.
  Read: [GB notes, sec. 7-7.4.5].

• Lecture 7 (10/18/2001). Specific efficient encryptions. ElGamal scheme and the DDH assumption. Application: Diffie-Hellman key exchange. Stronger notion: CPA security, definition and separation from PK-only. Notice that all results (BG + 1-bit=>many-bits + ElGamal) still work in CPA.
  Read: [GB notes, sec. 7-7.4.5].

• Lecture 8 (10/25/2001). Semantic security. Simulators and their importance. Equivalence to CPA definition. Private-Key Encryption. One-time definition and scheme. CPA definition and closure under composition. Stateful schemes (stream ciphers) based on forward-secure PRGs.
  Read: [GB notes, sec. 7.3.2, 7.5, 6.1, 6.3, 6.5-6.7, 6.12.2].

• Lecture 9 (11/01/2001). Towards stateless schemes: pseudorandom functions (PRFs). Definition, construction using PRGs, Naor-Reingold construction using DDH. Properties of PRFs. Applications: friend-and-foe, secret-key encryption. CTR and XOR schemes, their comparison. Birthday attack. Stream vs. Block Ciphers.
  Read: [GB notes, sec. 5-5.3, 5.6.1, 5.9, 5.11-5.12, 6.2, 6.8, 6.12.1]

• Lecture 10 (11/08/2001). 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. CPA-security of CFB,OFB,CBC modes. Exact security and its importance. Practical ciphers: DES, AES. Integration of symmetric and asymmetric encryption schemes.
  Read: [GB notes, sec. 5.4, 5.6.2, 5.10, 4-4.4, 6.2, 6.8-6.9]

• Lecture 11 (11/15/2001). 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) and e-xor-universal hash functions. Examples of UHFs: information-theoretic examples, XOR-MAC, CBC-MAC. A glimpse at CCA security and using MAC to go from CPA to CCA.
  Read: [GB notes, chap. 8, sec. 6.10-6.11]

• Lecture 12 (11/29/2001). 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. Universal one-way hash functions (UOWHF) and Collision-resistant hash functions (CRHF). Hash-then-sign paradigm for one-time and regular signature schemes.
  Read: [GB notes, sec. 9-9.3, 9.4.6]

• Lecture 13 (12/6/2002). Construction of UOWHFs using OWPs and universal hash functions. Construction of CRHFs under discrete log. Composition paradigms for UOWHFs and CRHFs. Comparing UOWHFs and CHRFs. Random oracle model and practical hash-then-sign signatures: full domain hash. Practical signature without random oracles: Cramer-Shoup scheme.
  Read: [GB notes, sec. 9.5-9.5.7, 9.5.12]

• Lecture 14 (12/12/2002). 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. Introduction to Zero-Knowledge (ZK). Motivation and quadratic residue example. Proof that NP belongs to CZK using commitments. Making password authentication with OWFs or commitments an identification scheme using ZK.

• What's next? (never happened). Many things we did NOT cover... More ZK. Protocols - huge! Identification protocols, OT and PIR, RO model (incl. OAEP and Fiat-Shamir heuristics), CCA and non-malleability, 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-commerse, anonymity (incl. pseudonyms, mix-nets), electronic voting, key exposure (incl. forward and bidirectional security), broadcast encryption/traitor tracing...

Last modified: December 31, 2001