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.
- Lecture 1 (9/4/2002).
Problem of secret communication. ``Classical'' schemes and attacks on
these schemes. One-time pad and Shannon's definition of perfect
- Lecture 2 (9/9/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 3 (9/11/2002).
Applications: UNIX password authentication, S/Key multi-time password
system. First proof by a reduction.
- Lecture 4 (9/16/2002).
Cryptographic proof methodology and logic:
Intuition->Definition->Scheme under some assumption->Proof of security
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).
- Lecture 5 (9/18/2002).
Public- vs. Secret-key cryptography. Trapdoor Permutations. Problems
with using iterated one-way/trapdoor permutations. Motivation to
Definition and general construction (Goldreich-Levin).
- Lecture 6 (9/23/2002).
Guest lecture: introduction to computational number theory.
Facts about arithmetic modulo a prime, and modulo composite.
Reference: Number theory primer
- Lecture 7 (9/25/2002).
Guest lecture: computational number theory. More
facts about arithmetic modulo a prime and composite.
Various OWFs/OWPs/TDPs including modulo exponentiation, squaring.
Reference: Number theory primer
- Lecture 8 (9/30/2002).
Chinese remaindering and its applications. RSA. Hardcore bits for
discrete log, squaring and RSA.
Reference: Number theory primer
- Lecture 9 (10/2/2002).
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 computational
- Lecture 10 (10/7/2002).
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 11 (10/9/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 12 (10/14/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. Stateless encryption of multiple
messages? Motivation for pseudorandom functions (PRFs).
- Lecture 13 (10/16/2002).
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 14 (10/21/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 15 (10/23/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 16 (10/28/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 17 (10/30/2002).
Message authentication schemes. Difference between privacy and
authenticity. Sending message in the clear -- message authentication
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.
- Lecture 18 (11/4/2002).
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 19 (11/6/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 20 (11/11/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
- Lecture 21 (11/13/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 22 (11/18/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 23 (11/20/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),
- Lecture 24 (11/25/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:
- Lecture 25 (11/27/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 26 (12/2/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 27 (12/4/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
- Lecture 28 (12/9/2002).
Identification Schemes. Brief definitions (key-only, passive, active),
several constructions (from signature and encryption; works for both
public- and symmetric key). Identification from 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
Last modified: December 9, 2002