CMSC858K --- Spring 2004 --- Lecture Schedule
Remark: The references listed below are for instructional purposes only.
They are not meant to provide exhaustive references for a particular area of research, often do not mention all of the earlier contributions, and sometimes do not list the most recent, "state-of-the-art" results. If you are interested in exploring a particular topic in more depth, I can suggest additional references.
Also, we may not cover all the listed references in class.
- [Lecture 1] Introduction and Preliminaries; Public-Key Encryption
Introduction. Expectations and course requirements.
Security parameters, poly-time computation, and negligible functions.
Motivating public-key encryption.
Two definitions of trapdoor permutations.
Syntactic definition of public-key encryption.
- [Lecture 2] Hard-Core Bits and Public-Key Encryption
Definition of semantic security/indistinguishability for public-key encryption.
A naive encryption scheme based on trapdoor permutations, and why it is insecure.
Hard-core bits from any trapdoor permutation.
Constructing a secure public-key encryption scheme for 1-bit messages.
- Hard-core bits: Goldreich-Levin '89, Goldreich (Section 2.5)
- Definitions of security for public-key encryption: Goldwasser-Micali '84, Bellare, et al. '98.
- [Lecture 3] Public-Key Encryption for Multiple Messages
A definition of security when multiple messages are encrypted.
Proof that the basic definition of security implies this, seemingly-stronger definition.
Computational indistinguishability and hybrid arguments.
- [Lecture 4] (More) Efficient Public-Key Encryption
Remarks on the efficiency of public-key encryption (encrypting long messages, achieving optimal ciphertext length, "hybrid" encryption).
Computational assumptions in finite, cyclic groups.
El Gamal encryption and a proof of security based on the DDH assumption.
- [Lecture 5] Chosen-Ciphertext Attacks and NIZK
Motivation for considering chosen-ciphertext attacks, and the difficulty of proving security in this setting.
Definition of chosen-ciphertext security for public-key encryption.
Review of P, NP, and NP completeness.
Brief discussion of interactive proofs and examples.
Informal discussion of (interactive) zero-knowledge proofs.
Definition(s) of NIZK proofs.
- Non-interactive zero-knowledge was introduced by Blum-Feldman-Micali '88 and Blum-De Santis-Micali-Persiano '91.
- A construction based on general assumptions (and also the first construction allowing the proof of polynomially-many statements) was first given by Feige-Lapidot-Shamir '90.
(The journal version of this last work appeared in '99, and some of the results are also in Feige's thesis.)
- Goldreich (Section 4.10) discusses NIZK in some detail as well.
- [Lecture 6] Chosen-Ciphertext Security
Adaptively-secure NIZK. A construction of a public-key encryption scheme secure against non-adaptive chosen-ciphertext attacks.
References: The encryption scheme discussed in class was proposed by Naor and Yung in 1990.
- [Lecture 7] Chosen-Ciphertext Security
Completing the proof of non-adaptive chosen-ciphertext security for the Naor-Yung construction.
A counterexample showing that the scheme is not secure against adaptive chosen-ciphertext attacks. Digital signature schemes.
A cryptosystem secure against adaptive chosen-ciphertext attacks.
References: For more detail about digital signature schemes (and their construction from one-way permutations) you can look at my lecture notes for CMSC 456.
The encryption scheme introduced in class is due to Dolev, Dwork, and Naor '91. I mentioned in class that it is possible to extend the Naor-Yung construction (by using a stronger form of NIZK proof) to achieve adaptive chosen-ciphertext security. This appeared in Sahai '99 (and was later simplified by Lindell '03).
- [Lecture 8] Chosen-Ciphertext Security; More on NIZK
Completing the proof of adaptive chosen-ciphertext security for the Dolev-Dwork-Naor construction.
Introduction to one-way functions, one-way permutations, and pseudorandom generators (if time).
- [Lectures 9-10] The Cramer-Shoup Encryption Scheme
Full proof of security for the Cramer-Shoup encryption scheme, building up from simpler schemes that are semantically-secure and CCA1-secure.
References: The scheme discussed in class is by Cramer-Shoup '98; their original paper is available here and a full version is available from the eprint archives.
Extensions of their scheme based on alternate number-theoretic assumptions are given by Cramer-Shoup '02, Gennaro-Lindell '03, and Camenisch-Shoup '03.
- [Lecture 11] Back to NIZK
Review of Cramer-Shoup encryption scheme. Introducing the "hidden bits" model for NIZK and converting any NIZK proof system in this model to one in the real model, using trapdoor permutations.
References: Our discussion of NIZK is drawn from the work of Feige-Lapidot-Shamir (Lapidot-Shamir '90, Feige-Lapidot-Shamir '90, and Feige-Lapidot-Shamir (journal version) '99) and is also based on Goldreich Section 4.10.
- [Lecture 12-13] Constructing NIZK
More on the conversion from the "hidden bits" model to the real model. Constructing NIZK in the "hidden bits" model. Pseudorandom generators. Adaptively-secure NIZK.
References: See references for the previous lecture
- [Lecture 14] NIZK; the Random Oracle Model
The random oracle model: pros and cons.
Encryption in the RO model.
- [Lecture 15] CCA2-secure encryption in the RO model
Simple CCA2-secure encryption in the RO model. OAEP and OAEP+.
References: OAEP was introduced by Bellare and Rogaway in Eurocrypt '94. The scheme discussed in class was OAEP+ and was introduced by Shoup in Crypto 2001.
- [Lecture 16] Signature Schemes in the RO model
The Lamport one-time signature scheme, based on one-way functions in the standard model.
The full-domain-hash (FDH) signature scheme, based on trapdoor permutations in the RO model.
An improved security analysis of FDH based on RSA.
References: Lamport's scheme was introduced in a technnical report from 1979. The FDH construction was given by Bellare and Rogaway in ACM CCCS '93. The improved analysis of FDH using RSA was done by Coron in Crypto 2000.