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
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
- Lecture 1 (9/6/2006)
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
notes, chap. 1,
sec. 6.3-6.4, 2.1-2.2].
- Lecture 2 (9/13/2006)
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''.
notes, sec. 2.3, 7.2].
- Lecture 3 (9/20/2006)
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
- Lecture 4 (9/27/2006)
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.
sec. 2.4, 3.0-3.2].
- Lecture 5 (10/4/2006)
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
notes, sec. 3.3-3.4].
- Lecture 6 (10/11/2006)
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
notes, sec. 7-7.4.5].
- Lecture 7 (10/18/2006)
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.
notes, sec. 10.1, 6.1, 6.3, 6.5].
- Lecture 8 (10/25/2006)
Stateful schemes (stream ciphers) based on forward-secure PRGs.
Towards stateless schemes: pseudorandom functions (PRFs). Definition,
construction using PRGs, Naor-Reingold construction using
notes, 6.1, 6.3, 6.5-6.7, 6.12.2, 5-5.3].
- Lecture 9 (11/01/2006)
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.
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)
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).
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)
Examples of UHFs: information-theoretic examples, XOR-MAC, CBC-MAC,
HMAC. Another XOR-MAC and e-xor-universal hash functions.
notes, chap. 8]
- Lecture 12 (11/29/2006)
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
notes, sec. 9-9.3]
Last modified: December 4, 2006