CSCI 5440: Cryptography

The Chinese University of Hong Kong, Spring 2011

• Lectures Wed 11:30-2:30 in ERB 405
• Instructor Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926
• Office hours Fri 10.30-12.30 (or by appointment)

Recent Announcements

• Apr 21 Take a look at the presentation schedule. Among the presentations on a similar topic (e.g. cryptography and game theory) you should do them in the order that makes most sense for the audience.
• Apr 21 The final project presentations will be on Wed Apr 27, 12.00-2.30 and Thu Apr 28, 11.30-2.15. You are expected to attend all the presentations (unless you have a conflict).
• Apr 21 The project report (about 5 pages long) should be turned in by Tue May 3.
• Apr 15 Homework 3 is due on Wed Apr 27. It has only two problems.

Course Description

Cryptography allows us to achieve secure and private communication over insecure channels. When used improperly, however, it can result in stolen credit card numbers, leakage of embarrassing secrets, impersonations, and so on. The objective of this course is to understand the foundations that allow the secure building of cryptosystems, with an emphasis on rigorous definitions and proofs of security and a critical eye towards the assumptions that allow us to achieve various forms of cryptography.

Lectures

This is a tentative schedule of the lectures. Changes are possible depending on progress and interest.

	date	topic	reading
1	Jan 12	What is cryptography? The one-time pad. Computational assumptions.	[pdf]
2	Jan 19	Message indistinguishability and semantic security. Pseudorandom generators. Private-key encryption.	[pdf]
3	Jan 26	Pseudorandom functions. Chosen plaintext attacks.	[pdf]
	Feb 2	No class, lunar new year
4	Feb 11	Construction of pseudorandom functions. Message authentication. Chosen ciphertext attacks.	[pdf]
5	Feb 16	Construction of CCA-secure encryptions. Variable-length MACs.	[pdf]
6	Feb 23	Cryptographic hash functions. One-way functions and pseudorandom generators.	[pdf]
7	Mar 2	The Goldreich-Levin theorem.	[pdf]
8	Mar 9	Public-key encryption.	[pdf]
9	Mar 16	Oblivious transfer and secure two-party computation.	[pdf]
	Mar 23	No class
	Mar 30	No class
10	Apr 6	Two-party protocol for honest-but-curious adversaries. Bit commitment and coin flipping.	[pdf]
11	Apr 13	Zero-knowledge proofs.	[pdf]
12	Apr 20	Enforcing honesty in two-party computation.	[pdf]
	Apr 27 Apr 28	Project presentations

Homeworks and Exams

• Homework 3 due Wed Apr 27
• Midterm exam due Mon Mar 14
• Homework 2 due Wed Mar 2
• Homework 1 due Wed Feb 16

Course Information

• Prerequisites Basic probability and algorithms. A bit of complexity theory (P, NP, reductions) is also helpful. If you are not sure you know these topics please talk to me.
• Grading and homeworks Your grade will be determined from homeworks (30%), a take-home midterm exam (30%), and a final project (40%). Three homeworks will be issued throughout the semester. You are encouraged to collaborate on the homeworks as long as you write up your own solutions.
• Final project For your final project you will be expected to do some independent reading, a presentation in class, and a short report. A list of suggested projects and more details will be provided around the middle of the semester.

References

Notes will be provided for every lecture. A substantial part of the course will closely follow the topics in the first book. The second and third books are great references for the theory of cryptography and cover much of the remaining material.

• Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. Chapman & Hall / CRC, 2007.
• Oded Goldreich. Foundations of Cryptography, volume 1: Basic Tools. Cambridge University Press, 2001.
• Oded Goldreich. Foundations of Cryptography, volume 2: Basic Applications. Cambridge University Press, 2004.