Lecture Schedule

Note: You are responsible only for the material covered in class. Items marked "reading" are expected to reinforce the material covered in class, but many times I will cover things in class that are not in the reading. Sometimes the reading will contain topics that I did not cover in class; in these cases, you are not responsible for the additional material.

Items marked "additional references" are meant to provide an alternate look at the same material. Some (e.g., [B], [TW]) give a more basic, less formal, or alternate presentation of material covered in class. Others (e.g., [GB], journal articles) give a more in-depth treatment for advanced students interested in topics only briefly mentioned in class. Again, you are only responsible for what is covered in class.

All references are listed on the suggested readings page.

Entires above the horizontal line reflect what was actually covered in class. Entries below the horizontal line reflect what I intend to cover in future classes.

Remark: The references listed below are for instructional purposes only. They are not meant to provide exhaustive references for a particular area of research, do not mention all of the earlier contributions, and do not list the most recent, "state-of-the-art" results. See me for more thorough references.

[Sept 4: Lecture 1] Introduction and "Classical" Cryptography
Introduction to the course. Motivation. Notation for encryption schemes, and definition of correctness. Discussion of a "classical" cryptographic scheme: the shift cipher. "Breaking" the shift cipher. What does it mean for an encryption scheme to be secure?
Reading: Stinson 1.1.1, 1.2.1.
Additional References: [B - chap. 1] [TW - chap. 2] [Kahn]
[Sept 6: Lecture 2] "Classical" Cryptography and Perfect Security
More on definitions of security. The Vigenere cipher. Motivation for provable security. The one-time pad and proof of security.
Reading: Stinson 1.1.4, 2.1 - 2.3
Additional References: Stinson 1.2.3; [B - chap. 1] [TW - chap. 2] [Kahn]
[Sept 9: Lecture 3] Perfect Security
Full proof of security for the one-time pad. Proof that the one-time pad is optimal. More insidious methods of attack and how to "break" the one-time pad. Where do we go from here? New definitions of perfect security and how to relax these to get an attainable definition.
Reading: Stinson 1.2.0
Additional References: [GB - chap. 6.4]
[Sept 11: Lecture 4] Computational Security: An Introduction
More on the definition we gave at the end of last class. The notion of probabilistic polynomial-time (PPT) algorithms and negligible functions. Re-writing the definition to include these elements. A complexity-theoretic notion of security. One-way functions and permutations. Probabilistic notation. Can we view factoring as a one-way function?
Reading:
References: [GB - chaps. 2.1-2.3]
[Sept 13: Lecture 5] Looking for Computational Hardness
Viewing multiplication as a one-way function if factoring is hard. Some number theory. Modular arithmetic, groups Z_p (p prime) and Z_N (N a product of primes), Chinese remaindering.
Reading: Handout on algebra; Stinson 5.2, 5.4, 5.5; [BR - chap. 3] [GB - Appendices B.1, B.2.1, B.2.2]
Additional References: [Ang] [GB - chaps. 2.2, 2.3] [Ch]
[Sept 16: Lecture 6] Deterministic Primality Testing, guest lecture by Prof. Gasarch
A few months ago, a long-standing problem in theoretical computer science was solved. Namely, a deterministic polynomial-time algorithm was given for determining whether a number is prime. We will review the main techniques used in this algorithm.
Reading: Lecture notes, by Prof. Gasarch
Additional References: Read the original paper. Additional information is also available.
[Sept 18: Lecture 7] Number Theory and Computational Hardness
More on Chinese remaindering. Jacobi and Legendre symbols, quadratic residues. Candidate one-way functions: squaring, RSA, discrete logarithm.
Reading: Handout on algebra; Stinson 5.2, 5.4, 5.5; [BR - chap. 3] [GB - Appendices B.1, B.2.1, B.2.2]
Additional References: [Ang] [GB - chaps. 2.2, 2.3] [Ch]
[Sept 20: Lecture 8] One-Way Functions from Number Theory
Proving that squaring is hard iff factoring is hard. The RSA one-way permutation.
Reading: Number theory references from above
[Sept 23: Lecture 9] One-Way Functions from Number Theory
The RSA one-way permutation and discrete logarithm one-way function. Our goal: define a pseudorandom generator in such a way that we can use it in the one-time pad construction yet beat the complexity of the one-time pad!
Reading: Number theory references from above
[Sept 25: Lecture 10] Pseudorandom Generators and Their Uses
Finding the "right" definition of a pseudorandom generator (PRG). Using a PRG to construct an encyption scheme that beats the one-time pad!
[Sept 27: Lecture 11] More Efficient PRGs
Encrypting messages one bit longer than the key is nice, but can we do better? We discuss constructing a PRG that stretches its input by two bits using as a building block a PRG that stretches its input by one bit. We also give a detailed proof of security for one construction in class; you will analyze another construction on the homework (grad students only).
[Sept 30: Lecture 12] Constructing PRGs
PRGs that stretch their input by any polynomial amount. Unpredictability. Hard-core bits. Existence of a hard-core bit for any one-way permutation. Constructing a PRG based on any one-way permutation.
Reading: Stinson 5.9.1
Additional References: Handouts on hard-core bits (by L. Trevisan) and pseudorandom generators; [B - chap. 3] [GB - chaps. 2.4, 3] [more advanced notes on hard-core bits by M. Bellare]
[Oct 2: Lecture 13] Wrapping Up PRGs
Completing the proof for the construction of a PRG based on any one-way permutation. Note that PRGs exist if and only if one-way functions exist. Recap for private-key encryption: Alternate way of viewing security via left-or-right indistinguishability and access to an encryption oracle. Extending the definition to model chosen plaintext attacks.
[Oct 4: Lecture 14] Private-Key Encryption and PRFs
Deterministic vs. randomized encryption; limits on what deterministic encryption can achieve. Introduction to pseudorandom functions (PRFs) and random functions.
Reading:
Additional References: [B - chaps. 2,4.1-4.6, 4.7.4, 4.7.5] [GB - chaps. 5.1-5.4, 5.6, 5.7, 5.10]
[Oct 7: Lecture 15] PRFs and PRPs
PRFs, pseudorandom permutations (PRPs), and strong PRPs. Constructing PRFs and strong PRPs based on one-way functions. Block ciphers.
Reading:
Additional References: [B - chaps. 2,4.1-4.6, 4.7.4, 4.7.5] [GB - chaps. 5.1-5.4, 5.6, 5.7, 5.10, 6] [Stinson 3.5, 3.6]
[Oct 9: Lecture 16] Achieving Indistinguishable Private-Key Encryption
An indistinguishable encryption scheme (our first!) based on any PRF.
Reading:
Additional References: [B - chaps. 2,4.1-4.6, 4.7.4, 4.7.5] [GB - chaps. 5.1-5.4, 5.6, 5.7, 5.10, 6]
[Oct 11: Lecture 17] Finishing up Private-Key Encryption
Modes of encryption for encrypting long messages.
Reading: Stinson 3.7
[Oct 14: Lecture 18]-[Oct 16: Lecture 19] (Private-Key) Message Authentication
Definition of security for message authentication. Message authentication using PRFs.
Reading: Stinson 4.1, 4.4
Additional References: [B - chap. 5] [GB - chap. 8] [BKR94] [BGR95]
[Oct 18: Lecture 20] Midterm Review
I will briefly discuss what material will be covered on the exam, and will then take questions on what we have covered in class thus far. Please bring your questions! If there are no questions, we will cover new material.
[Oct 21: Lecture 21] Midterm Exam
Covers material up to (and including) lecture 20.
[Oct 23: Lecture 22] Message Authentication Codes
MACs used in practice: XOR MAC (finish up from last time), CBC MAC. Collision-resistant hash functions.
[Oct 25: Lecture 23] More on Message Authentication
Hash-and-MAC using collision-resistant hash functions. An appropriate definition for MACs with perfect security.
[Oct 28: Lecture 24] Perfect Message Authentication
Introduction to finite fields. Schemes for perfect message authentication.
[Oct 30: Lecture 25] Algorithmic Number Theory
Groups, fields. Efficient computation with large integers (addition, multiplication, exponentiation, gcd computation, modular arithmetic, square roots, chinese remaindering, etc.).
Reading: Stinson 5.2, 5.4, 5.5, 5.8; handout on algebra
Additional References: [GB - chaps. 2.3, Appendix C] [TW - chaps. 3.1, 3.3-3.7, 3.9, 3.10] [Ch]
[Nov 1: Lecture 26] Primality Testing
Two primality testing algorithms and comments on their performance.
[Nov 4: Lecture 27] Introduction to Public-Key Encryption
Motivation for public-key cryptography and relationship to private-key cryptography
[Nov 6: Lecture 28] Definitions of Public-Key Encryption
Can perfect security be achieved? Can deterministic public-key encryption schemes exist? We give a reasonable definition of security for public-key encryption schemes.
[Nov 8: Lecture 29] Construction of a Secure Public-Key Encryption Scheme
Scheme based on the quadratic residuosity problem. Proof of security.
[Nov 11: Lecture 30] Diffie-Hellman Problems
Discrete logarithm, CDH, and DDH problems, and their relation. The El Gamal encryption scheme.
[Nov 13: Lecture 31] Public-Key Encryption...
Proof of security for El Gamal encryption. El Gamal encryption in practice. A stronger definition for public-key encryption? Showing that that this definition is equivalent to our previous definition.
[Nov 15: Lecture 32] Indistinguishability
Proof that indistinguishability is equivalent to our previous definition. The value of this result. Introduction to hybrid encryption.
[Nov 18: Lecture 33] Hybrid Encryption
How to make public-key encryption more efficient (in both communication and computation). Proof of security.
[Nov 20: Lecture 34] Trapdoor permutations and PKE
Definition of trapdoor permutations, examples. Constructing a public-key encryption scheme from any trapdoor permutation. Improving the efficiency of the construction.
[Nov 22: Lecture 35] Signature schemes I
Motivation, definitions of security for signature schemes and 1-time signature schemes. The suggestion of Diffie and Hellman and why this does not work; why "textbook" RSA is insecure. The Lamport 1-time signature scheme.
Reading: Stinson 7.1, 7.2, 7.5
Additional References: [B - chap. 7]; Stinson 7.3, 7.4; [TW - chap. 8.1-8.3, 8.5] [GB - chap. 9]
[Nov 25: Lecture 36] Signature schemes II
Proof of security for the Lamport 1-time signature scheme. Extending the scheme: improving the efficiency, using the scheme to sign more than one message.
[Nov 27: Lecture 37] Signature Schemes for Multiple Messages
A tree-based scheme for more efficient signatures. Removing state. Using universal one-way hash functions instead of collision-resistant hash functions.
[Nov 29 - Thanksgiving Recess]
[Dec 2: Lecture 38] Signature Schemes for Multiple Messages II
[Dec 4: Lecture 39] Introduction to the Random Oracle Model
Introduction to the Random Oracle (RO) model and comparison to the "standard" model. Implementation of the RO model. Security in the RO model. The Full Domain Hash signature scheme and a proof of security.
[Dec 6: Lecture 40] Class Cancelled
[Dec 9: Lecture 41] The Random Oracle Model
An improved proof of security for the Full Domain Hash signature scheme using RSA.
Reading: Stinson 4.2
Additional References: [BR93] [GB - chaps. 9.7, 9.9]
[Dec 11: Lecture 42] Advanced Topics
A secure and efficient encryption scheme based on any trapdoor permutation (e.g., RSA) in the RO model. Definitions and models of security for identification schemes ("basic" adversary, passive adversary, active adversary).
[Dec 13: Lecture 43] Final Review
Please bring your questions about any material covered this semester! If there are no questions, I will cover new material.
[Dec 21] Final Exam
Given from 8-10AM in room CSIC 1121