CSCI 5440: Cryptography

Final project information

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.

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.

Presentation Schedule


Wednesday 27 April in room ERB 405

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


Thursday 28 April in room ERB 405

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




Possible topics

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

One-way functions and pseudorandom generators

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.

• Haitner, Reingold, Vadhan: Efficiency improvements in constructing pseudorandom generators from one-way functions
• Haitner, Harnik, Reingold: On the power of the randomized iterate




Composable security

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 / very efficient cryptography

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.

• 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




Cryptography and game theory

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:

• 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




Obfuscation

The task of obfuscation is to hide the "source code" of a program without changing its functionality.

• Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang: On the (im)possibility of obfuscating programs




Cryptographic hardness for learning algorithms

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.

• Kearns and Valiant: Cryptographic Limitations on Learning Boolean Formulae and Finite Automata