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 (1/25/2012).
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
Read: [Katz-Lindell, chap. 1,2], [Boneh-Shoup, sec 2.1,2.2]
- Lecture 2 (2/1/2012)
One-way functions and permutations. Collections of OWFs/OWPs.
Applications: UNIX password authentication,
S/Key one-time password system.
Cryptographic assumptions and proof by reduction. Formal security
proof for S/Key.
Read: [Katz-Lindell, sec 3.1, 6.1.1-6.1.2, 7.4.1]
- Lecture 3 (2/8/2012)
Brish-up on number theory. Primes vs. composites, easy and hard
problems. RSA, discrete log, factoring, square root extraction.
Chinese remainder theorem. Examples of OWFs (integer multiplication,
squaring mod n), OWPs (modular exponentiation) and TDPs (RSA, Rabin).
Read: see number-theoretic handouts in the
section, [Katz-Lindell, sec. 7].
- Lecture 4 (2/15/2012)
Trapdoor permutations. Toy PKE. Main problems and criticism of
one-way functions: reveal partial information, not ``pseudorandom''.
Motivation to hardcore bits. Examples: MSB for discrete log, LSB for
squaring. Definition. General construction (Goldreich-Levin). [maybe:
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.
[Katz-Lindell, 6.1.3, 6.3, 3.3, 3.4.1], [Boneh-Shoup, 21.2].
- Lecture 5 (2/22/2012)
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
Read: [Katz-Lindell, 3.3, 3.4.1, 6.4],
[Boneh-Shoup, 3.1, 3.4-3.5]
- Lecture 6 (2/29/2012)
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
Read: [Katz-Lindell, 10.1, 10.2, 10.4, 10.7],
[Boneh-Shoup, 10.1-10.4, 11.1-11.3]
- Lecture 7 (3/2/2012)
Semantic security and its equivalence to CPA indistinguishability.
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
Read: [Katz-Lindell, 3.2.2, 10.5, 10.7, 9.3, 9.4],
[Boneh-Shoup, 10.5-10.6, 11.4-11.5]
- Lecture 8 (3/7/2012)
Symmetric-Key Encryption. One-time definition and scheme. CPA
definition and closure under composition.
Stateful schemes (stream ciphers) based on forward-secure PRGs.
Towards stateless schemes: pseudorandom functions (PRFs). Definition,
construction using PRGs, Naor-Reingold construction using
Read: [Katz-Lindell, 3.2-3.4, 6.5], [Boneh-Shoup, 3.1-3.3, 4.4., 4.6,
- Lecture 9 (3/21/2012)
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: [Katz-Lindell, 3.5-3.6, 6.6], [Boneh-Shoup, 4.1, 4.3, 4.5, 5.2-5.4]
- Lecture 10 (3/28/2012)
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: [Katz-Lindell, 3.6, 4.1-4.4], [Boneh-Shoup, 5.4, 6.1-6.2, 7.1,
- Lecture 11 (4/4/2012)
Examples of UHFs: information-theoretic examples, XOR-MAC, CBC-MAC,
HMAC. Another XOR-MAC and e-xor-universal hash functions.
Variable-length messages. CCA security for symmetric
encryption. Example PRP(m|r). Authenticated encryption. AE implies
CCA security. Encrypt-then-MAC method. More advanced methods.
Read: [Katz-Lindell, 4.5, 4.7-4.9, 3.7], [Boneh-Shoup, 7.2-7.5,
6.3-6.6, 6.10, 8.7, 9.1-9.3]
- Lecture 12 (4/11/2012)
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). Hash-then-sign paradigm.
Read: [Katz-Lindell, 4.6, 12.1-12.4], [Boneh-Shoup, 8.1-8.5, 10.8, 13.1-13.2]
- Lecture 13 (4/18/2012)
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.
Random oracle model and practical hash-then-sign signatures: full
domain hash. Practical signature without random oracles: Cramer-Shoup
Read: [Katz-Lindell, 12.5-12.6, 12.8, 13.1, 13.3], [Boneh-Shoup,
- Lecture 14 (4/25/2012)
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,
- Lecture 15 (5/2/2012)
Introduction to Zero-Knowledge (ZK). Proofs and class NP. Interactive
protocols and class IP. Importance of randomness. IP=PSPACE. IP for
GNI (graph non-isomorphism). Moving to ZK. ZKIP for GNI (graph
isomorphism). ZK for all NP (even IP!) from commitments (<=>
OWF). ZKIP for 3-colorability (w/efficient prover). Honest Verifier ZK
(HVZK) vs ZK. Proofs of Knowledge (PoK). Sequential and parallel
repertition (for ZK/HVZK and Soundness/PoK). Sigma-Protocols, closure
properties. Sigma-protocol for DL. Constant-Round ZKIP (+PoK) for NP
w/negl. soundness. Concurrency, CRS model. Intro to concurrent ZK
(trapdoor commitments), NIZK (Fiat-Shamir, FLS), deniability and
Last modified: May 2, 2012