Web Application for Privacy-Preserving Assignments

Master Thesis

Author

Tariq Taha

Motivation

The assignment problem is a combinatorial optimization problem which can be solved in polynomial time using the Hungarian algorithm. An example for this problem is as follows: n students register for a seminar where n topics are available. The students provide their preferences to all available topics, which are associated with some costs (the happiness of the student when assigned to that topic): e.g., a student's first preference will cost n, while his/her least preference will cost 1. Any student can be assigned to any topic, all topics have to be assigned exactly to one student and each student needs to be assigned to exactly one topic in such a way that the total cost (happiness) is maximized. Such assignment problems can be solved without using a trusted third party in a privacy-preserving manner. In order to achieve this, secure computation techniques can be utilized. The main goal is to enable students to bid for their preferred topics and get the result without anyone else learning their preferences.

Goal

The goal of this thesis is to develop a web application where students for a seminar can bid for their preferred topics and their assignments are computed in a privacy-preserving manner. This is achieved by secret-sharing the bids among two non-colluding servers, which then perform secure two-party computation to solve the assignment problem.

Requirements

Applicants should have outstanding academic records and solid C/C++ programming skills and should have basic knowledge of JavaScript to develop the web application.

Tasks

For the secure computation part, the student should take a C implementation of the Hungarian algorithm, generate a Boolean circuit corresponding to it using an automated compiler and evaluate it using the ABY secure computation framework [DSZ15]. Moreover, the student should develop a web application that takes care of the secret sharing on the user's side in JavaScript.

Depending on the type of the thesis, possible example extensions are: Given different number of student and topics, group together students to work on the same topic, or decide which topic should be excluded such that the happiness is maximized. This can be further constrained by grouping together topics and allowing topics to be excluded only if the exclusion happens uniformly distributed over the different groups, etc.

References

  • [DSZ15]: Daniel Demmler, Thomas Schneider and Michael Zohner: ABY – A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In NDSS'15.

Supervisors

Publications