Theoretical Cryptography (Spring 2020)

Basic Information

Instructor: Yu Chen, Email: yuchen.prc@gmail.com or cycosmic@gmail.com
Teaching Assistant: Binbin Tu, Email:
Place: 淦昌苑D座118 (青岛校区)
Time: 周二9-11, 周四3-4 (Week 3-12)

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: definition and construction
Hardcore Bits: 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)

Prerequisites

We will assume familiarity with basic (discrete) probability and modular arithmetic. Students enrolled are expected to have had some exposure to algorithms, mainly to be comfortable reading pseudocode and to be familiar with big-O notation.

Textbook and 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 (2nd Edition). 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
A Graduate Course in Applied Cryptography. By Dan Boneh and Victor Shoup

Grading and Policies

Homework: 30%
Reading Report + Presentation: 70%

The detailed requirement is here. Any late submission of the homework or report will NOT be accepted.