Course Information

The broad topic here is privacy-preserving computation, meaning how parties can compute joint functions of their data without revealing more than necessary about their data. In multi-party computation (MPC) the number of parties can be arbitrary. Two-Party Computation (2PC) is the special case of MPC where the number of parties is two. Within this, our focus is Private Set Intersection (PSI), the case of 2PC where the data held by a party is a set and the desired outcome is the intersection of the sets of the two parties. We pick this because it has a range of emerging applications and correspondingly is seeing a range of protocol solutions. So we will study PSI, but through it aim to also learn more about 2PC in general.

We are interested in a number of dimensions:

  • Protocols: How is PSI done? What are the different approaches, what are some specific protocol solutions? Let's try first to understand the simplest solutions, and then move to ones that may have better attributes in terms of cost or security.
  • Applications: How, and for what, is PSI used? Are the applications suggested in papers? Deployed in the real world? What other ways are there to solve the same problems? How effective are these applications at solving the problem?
  • Security: What definition of security is the protocol shown to meet? Can we understand the proof of security? What alternative definitions might one give?
  • Society: Who does PSI, or a particular application of it, benefit? Is it Power, or People?

The Private tab in the menu takes you to a set of Google Drive files accessible only to enrolled students. Here we will develop the presentation schedule, where your team can sign up. We will also develop a document with plans.

This is a seminar. Students will read and present papers. Students can work in teams of up to two people if they so desire. The resources pointer in the menu makes a start at some relevant pointers, but this is neither exhaustive nor binding. There are many possible modalities for your presentation. You can find, on YouTube, videos of conference presentations of papers on PSI. You could pick one and read the paper. In class, you could play the video, pausing it when appropriate to add your commentary and take interruptions and questions, and doing deeper dives based on your knowledge of the paper. Alternatively, you could use the WhiteBoard and present the chosen paper directly. Your presentation need not focus on a single paper. It could, for example, do some efficiency comparisons, discuss applications, discuss available software implementations, do a critical analysis. Your focus could be on the protocols, the definitions of security, the proofs of security, attacks or whatever other aspect engages you most.

Why should I take this class, you ask? See it as a community-building project where we come together to understand and learn about this topic, with the goal that it be a springboard for future research. As you look at, and discuss, papers, ask yourself, can one do better? What are the open questions? Are these good definitions, or can we come up with better ones? Can we improve the protocols? Can we find new applications? And so on.

Course requirements are a presentation and participation in discussion. You can take the class P/NP (S/U) or for a letter grade, and requirements may be higher in the latter case. The number of units for which you enrol may also be a choice, and again may affect the requirements. Auditing (not doing a presentation) is not encouraged; if you want to benefit from the presentations made by others, you should do one too. Pre-requisites are some knowledge of cryptography as given by CSE 207 or 207B; or CSE 107 with permission of Instructor; or permission of Instructor.

Piazza

We have a piazza for this class. This can be a medium for discussion.