**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)

**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.

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.

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] |

No class | |||

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 |

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

**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.

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.