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
Read: this web page,
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''.
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
- 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
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
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.
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.
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.
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.
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
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
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
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
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
Last modified: December 31, 2001