Theoretical Foundations of Cryptography (Spring 2018)
Instructor: Yu Chen (co-teach with Prof. Rui Xue)
Email: chenyu@iie.ac.cn or cycosmic@gmail.com
Course Information
Place: Teaching Building 1-305, Yanqi Lake, UCAS, Huairou, Beijing
Time: 13:30pm -- 16:20 pm, Tuesday (Week 1-15)
Course Description
Modern cryptography have been playing an important role in information security,
ranging from purely theoretical studies (e.g. complexity theory) to highly practical applications
(e.g. secure communication, Bitcoins, etc.) Research in the related fields has been extremely active since 1949.
This course 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.
We will introduce a variety of basic primitives/tools.
With each primitive, we will demonstrate its applications to see how it can be used
(either in practical protocols and or in higher-level schemes).
Here is a list of topics that we would like to cover.
(The syllabus can be found here as well.)
Please feel free to contact me if you have questions about the course.
- Introduction
- One-way functions: constructions of OWF and hardness amplification
- Goldreich-Levin theorem
- Indistinguishability and Pseudorandomness
- Pseudorandom generator (expansion theorem and 1-bit PRG from OWP)
- Pseudorandom functions/permutations (GGM construction and NR construction)
- Private-key encryption (perfect secrecy and CPA security)
- Message authentication code
- Authenticated encryption
- Digital signatures (OWF-based construction, chain-based and tree-based construction)
- Random oracle methodology
- Public-key encryption (CPA security, CCA security, Naor-Yung paradigm, DDN paradigm)
- Zero-knowledge protocols (identification protocol, HPS and EHPS)
- Other selected advanced topics if time permits (e.g. identity-based encryption, various functions)
Required Readings
There is no required textbook. The lectures will follow the following materials:
- Lecture notes: Theoretical Foundations of Cryptography. By Chris Peikert, Jonathan Katz
- Textbook: Introduction to Modern Cryptography. By Jonathan Katz and Yehuda Lindell
Supplementary/Recommended Readings
- Foundations of Cryptography. By Oded Goldreich
- Computational Complexity: A Modern Approach. By Sanjeev Arora and Boaz Barak