Master Thesis
Secret Santa using multiparty computation
Secret Santa is a famous Christmas tradition in which members of a group are randomly assigned a person to whom they give a gift. The assignments in total are not known by anyone in the group and should remain a secret. An extended version of the game also allows members to specify restrictions in the draw. Specifically, a member can specify an excluded subgroup and the game should make sure that this member is not assigned a person from the excluded subgroup.
Multiparty Computation (or MPC) enables a group of participants, who do not necessarily trust each other, to jointly perform a computation. The term was introduced by Yao in 1982[1]. The participants agree on a function to compute. Each participant holds an input to that function. Using an MPC protocol they compute the output of the function on their secret inputs without revealing them. A famous example, given in [1], is the Millionaires’ problem: “Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional
information about each other’s wealth.” In this case, the function they wish to compute is x_1 < x_2, where the first participant knows the input x_1 and the second knows x_2. For more information and some important MPC protocols we refer to the chapters 3.1 to 3.3 of the book in [2].
The goal of this thesis is to perform the Secret Santa random assignment using MPC. That is, a group of people, with each member possibly having some restrictions, performs the draw in a decentralized and distributed manner. The first step is to formalize the problem and to design an MPC implementation of it. As a second step, a prototype should be realized.
References
[1] Protocols for Secure Computations
[2] A Pragmatic Introduction to Secure Multi-Party Computation