CSCI 5440: Cryptography

The Chinese University of Hong Kong, Fall 2012

• Lectures Wed 10:30-1:30 in Esther Lee 307
• Instructor Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926
• Office hours Fri 10.30-12.30 (or by appointment)

Recent Announcements

• Dec 9 I made a few changes in the schedule, please take another look.
• Dec 7 Check the presentation schedule. It is pretty tight so please do not go overtime.
• Dec 7 Remember the project report should be turned in by Dec 12 in class or over email. It should not be too long (no more than 5 pages).
• Nov 28 The class presentations will take place in Esther Lee (ELB) 304 on 12 Dec from 9.30 until 1.30. Everyone is expected to attend all presentations.

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. If time permits we will also touch on some more recent topics like fully homomorphic encryption and database privacy.

Lectures

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

	date	topic	reading
1	Sep 12	What is cryptography? The one-time pad. Computational assumptions.	[pdf]
2	Sep 19	Message indistinguishability and semantic security. Pseudorandom generators. Private-key encryption.	[pdf]
3	Sep 26	Chosen plaintext attacks and pseudorandom functions.	[pdf]
4	Oct 3	Construction of pseudorandom functions. Message authentication. Chosen ciphertext attacks.	[pdf]
5	Oct 10	Construction of CCA-secure encryptions. Variable-length MACs.	[pdf]
	Oct 17	No class
6	Oct 24	Cryptographic hash functions. One-way functions and pseudorandom generators.	[pdf]
7	Oct 31	The Goldreich-Levin theorem.	[pdf]
8	Nov 7	Public-key encryption.	[pdf]
9	Nov 14	Public-key encryption from trapdoor permutations. Trapdoor permutatons based on hardness of factoring.
10	Nov 21	Digital signature schemes.	[pdf]
11	Nov 28	Database privacy: Definitions and the Laplace mechanism.	[pdf]
12	Dec 5	Database privacy: Sanitization and the Blum-Ligett-Roth mechanism.
	Dec 12	Project presentations in ELB 304

Homeworks and Exams

• Homework 3 due Wed Dec 5
• Midterm exam due Wed Nov 14
• Homework 2 due Wed Oct 31
• Homework 1 due Wed Oct 10

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.

Here are some notes on probability that refresh some basic concepts and explain the notation we use.