For your final project, you can do one of the following.

**Study a problem from your own research area from a cryptographic perspective.**For example, if you design or analyze computer systems, you can propose a cryptographic solution or analysis of system security. If you work in machine learning, you can discuss the implications of various cryptographic hardness assumptions to the learnability of various concepts (and maybe provide an implementation that illustrates this).**Study and reflect upon a topic in cryptography in your choice.**To do this kind of project, you will likely need to do some background reading (some projects require more than others). However I expect you to be*critical*: Try to identify issues/limitations of exisiting solutions and discuss alternative proposals. This is a research-oriented project. If you manage to succeed in producing an improvement great, but even if you don't I expect you to try different things and at least understand why they might not work.- Haitner, Reingold, Vadhan: Efficiency improvements in constructing pseudorandom generators from one-way functions
- Haitner, Harnik, Reingold: On the power of the randomized iterate
- Applebaum, Ishai, Kushilevitz: Cryptography in NC0
- Ishai, Kushilevitz, Ostrovsky, Sahai: Cryptography with constant computational overhead
- Benny Applebaum: Pseudorandom Generators with Long Stretch and Low locality from Random Local One-Way Functions
- Dodis, Halevi, Rabin: A Cryptographic Solution to a Game Theoretic Problem
- Gradwohl, Livne, Rosen: Sequential rationality in cryptographic protocols
- Kol and Naor: Cryptography and game theory: designing protocols for exchanging information
- Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang: On the (im)possibility of obfuscating programs
- Kearns and Valiant: Cryptographic Limitations on Learning Boolean Formulae and Finite Automata

You will need to write a short survey (due Apr 27) and give a 15 minute presentation on the last week of classes (to be scheduled). For your presentation you can either use slides or the whiteboard.

You can work individually or in pairs. Please let me know about your
project proposal by email by **Fri Mar 25**. You can write a
paragraph or two about your proposed topic.

12.00-12.15 | Hing Yin Tsang | One-way functions and pseudorandomness |

12.15-12.30 | Li Fan | One-way functions and pseudorandomness |

12.30-12.45 | Guo Siyao | Hardness amplification and extractors |

12.45-1.30 | break | |

1.30-1.45 | Chi Wang Chow | Subset sum based cryptosystems |

1.45-2.00 | Chuk Hin Chen | Homomorphic encryption |

2.00-2.15 | Xiaolei Wang | Program obfuscation |

2.15-2.30 | Li Jiang | Security for embedded systems |

11.30-11.45 | Zichao Yang | Cryptography and game theory 1 |

11.45-12.00 | Yeung Yuen Chuen | Cryptography and game theory 2 |

12.00-12.15 | Kwok Tsz Chiu | Cryptography and game theory 3 |

12.15-12.30 | Xie Hong, Yang Chen | Cryptography and game theory 4 |

12.30-1.15 | break | |

1.15-1.30 | Wong Chung Hoi, Wong Po Yuen | Cryptography and quantum games |

1.30-1.45 | Zechao Shang | Privacy |

1.45-2.00 | Bai Xue |

Here are some possible choices of topics. Feel also free to propose your own.

In principle, the existence of one-way functions is sufficient to construct pseudorandom generators. In practice, the constructions we know are quite inefficient. Are these inefficiencies inherent or can they be overcome? There has been some recent progress, but many obstacles remain.

In class we only considered stand-alone executions of cryptographic protocols. What happens when several protocols (or several runs of the same protocol) are executed concurrently? This is very relevant in practical scenarios like the internet. These references and lecture notes may be a good starting point for this topic.

Parallel cryptography attempts to come up with extremely efficient implementations of various cryptographic primitives and protocols. Sometimes it is possible, sometimes it isn't, and sometimes we don't know.

Cryptography and game theory share some similarities: Players engage into protocols from which they attempt to extract some utility. Sometimes cryptographic solutions can help in game theory, and vice versa. Here are some sample papers:

Machine learning is used everywhere from the internet to the stock market. On the other hand, cryptography provides examples of hard problems for learning algorithms. For example, pseudorandom functions are hard to learn, because given any observed collection of values it is hard to predict any other value. For this project you can try various implementations of learning algorithms and watch them fail on cryptographic inputs.