Distributed Private Stable Matching
Distributed Private Stable Matching
Sophia Lin, Lila Fontes
Suppose a group of people want to compute a function f(x1 ,x2 ,...,xn ). The task might be
easy if someone holds all of x1 ,x2 ,...,xn . But in our case, they each hold a different input, and do
not wish to share their inputs with others. Is it possible for them to compute the function? This is
the kind of problem that we study. It turns out that some of the functions on two inputs are not
privately computable, but the ones on multiple inputs are computable with Shamir’s secret
sharing, as long as they are based on addition and multiplication. In this project, we are
interested in the stable matching problem (which is often introduced in the first week of
algorithms).
In the first half of the summer, we designed a non-cryptographic protocol (using Shamir’s
secret sharing scheme) that helps agents on a synchronous distributed network privately find a
stable matching. There are usually more than one stable matching, given the agents’
preferences, but we only want to output one of them. A way to solve the problem is to randomly
choose from the stable matchings. However, such a protocol has a very high rounds complexity
(rounds complexity is what we use to measure the efficiency of a protocol). Another approach is
to output the stable matching that is optimal for one of the sides. This is less costly, but the
complexity is still higher than linear.
We spent the rest of our time trying to find a lower bound on the rounds complexity of the
problem. We need a lower bound technique that 1) works for multi-party, probabilistic protocols,
2) takes privacy into account. None of the existing techniques satisfy the requirements, so we
have to develop a new technique. A crucial step towards our goal is to characterize the private
computation of multi-party functions. We have yet to accomplish that.
