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.
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.
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.
- [DSZ15]: Daniel Demmler, Thomas Schneider and Michael Zohner: ABY – A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In NDSS'15.
- Ágnes Kiss, M.Sc. (email@example.com-…)
- Prof. Dr.-Ing. Thomas Schneider (firstname.lastname@example.org-…)
- Taha Tariq: Web Application for Privacy-Preserving Assignments. Master Thesis, 2018.