# CS 8803TFC - Theoretical Foundations of Cryptography, Spring 2010

## Contents |

## Course Information

**Instructor:** Chris Peikert

**Time:** Tue/Thu 9:35-10:55am (First meeting: Jan 12th)

**Location:** College of Computing building, room 53.

**Summary:** Cryptography, or "secret writing," is nearly as old as
written communication itself. Yet only over the past few decades has
it grown from a "black art" into a true science with rigorous
mathematical foundations and methodologies. These have taken
cryptography far beyond its roots in simple secret codes, to a
discipline with far-reaching influence on computing as a whole.

This class is a graduate-level, *theory-oriented* introduction to
the foundations of modern cryptography. The emphasis is on essential
*concepts*, precise *models and definitions*, and *proof techniques*. Topics include: one-way functions and related
complexity assumptions, pseudorandomness, public-key and
identity-based crypto, zero knowledge and commitment, and connections
to diverse areas of computer science. As time permits, we may also
touch upon specialized topic areas such as secure multiparty
computation, private information retrieval, or lattice-based
cryptography.

For more information and course policies, see the course information and syllabus handout.

## Assignments

## Handouts and Lecture Notes

- Lecture 1: Overview, Perfect Secrecy
- Supplementary reading: Section 1.3 of Pass-shelat

**Computational Hardness**

- Lecture 2: Limits of Perfect Secrecy, Computational Hardness
- Supplementary reading: Sections 2.1-2.2 of Pass-shelat

- Lecture 3: Candidate OWFs, Hardness Amplification
- Supplementary reading: Sections 2.3-2.5 of Pass-shelat

- Lecture 4: Number Theory, OWF Variants
- Supplementary reading: Section 2.6-2.7 of Pass-shelat

**Indistinguishability and Pseudorandomness**

- Lecture 5: Indistinguishability, Pseudorandom Generators
- Supplementary reading: Sections 3-3.3 of Pass-shelat

- Lecture 6: Expanding PRGs, Blum-Micali
- Supplementary reading: Sections 3.3-3.4.1 of Pass-shelat

- Lecture 7: Blum-Micali, Goldreich-Levin Theorem
- Supplementary reading: Section 3.4 of Pass-shelat, David Wagner's notes and Mihir Bellare's notes on GL

- Lecture 8: Pseudorandom Functions
- Supplementary reading: Section 3.8 of Pass-shelat

- Lecture 9: Symmetric Encryption
- Supplementary reading: Sections 3.5-3.7, 3.9 of Pass-shelat

- Lecture 10: Asymmetric Encryption
- Supplementary reading: Sections 3.10-3.11 of Pass-shelat

**Authentication**

- Lecture 11: Message Authentication
- Supplementary reading: Sections 5-5.2 of Pass-shelat

- Lecture 12: CCA Security, Digital Signatures
- Supplementary reading: Sections 5.3-5.4 of Pass-shelat

- Lecture 13: Digital Signatures
- Supplementary reading: Sections 5.5-5.7 of Pass-shelat

- Lecture 14: Random Oracle Signatures
- Supplementary reading: Sections 5.8 of Pass-shelat

**Zero Knowledge**

- Lecture 15: Zero Knowledge, Interactive Proofs
- Supplementary reading: Sections 4-4.5 of Pass-shelat

- Lecture 16: ZK Proofs
- Supplementary reading: Sections 4.5-4.6 of Pass-shelat

- Lecture 17: ZK for NP
- Supplementary reading: Section 4.7 of Pass-shelat

- Lecture 18: Proofs of Knowledge

- Lecture 19: ZK Potpourri

- Lecture 20: Secure 2-Party Computation

**Special Topics**

- Lecture 21: Identity-Based Encryption

- Lecture 22: Cramer-Shoup CCA-Secure Encryption

- Lecture 23: Lattice-Based Crypto I

- Lecture 24: Lattice-Based Crypto II

- Lecture 25: Lattice-Based Crypto III

- Lecture 26: Lattice-Based Crypto IV

- Lecture 27: The Frontier

## Useful Links

- The Georgia Tech cryptography reading group.

- A Course in Cryptography, by Rafael Pass and abhi shelat (freely available notes)

- Boaz Barak's course at Princeton

- Salil Vadhan's course at Harvard

- Yevgeniy Dodis's course at NYU

- A Computational Introduction to Number Theory and Algebra, a book by Victor Shoup (freely available)

- A collection of good advice on reading and writing mathematical proofs.

- A free, very thorough introduction to LaTeX, and good style tips.

## Archive

Previous iterations of this course: