International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Private and Efficient Stable Marriages (Matching)

Authors:
Timothy Atkinson
R. Bartak
Marius C. Silaghi
E. Tuleu
M. Zanker
Download:
URL: http://eprint.iacr.org/2006/345
Search ePrint
Search Google
Abstract: We provide algorithms guaranteeing high levels of privacy by computing uniformly random solutions to stable marriages problems. We also provide efficient algorithms extracting a non-uniformly random solution and guaranteeing t-privacy for any threshold t. The most private solution is expensive and is based on a distributed/shared CSP model of the problem. The most efficient version is based on running the Gale-Shapley algorithm after shuffling the men (or women) in the shared secret description of the problem. We introduce an efficient arithmetic circuit for the Gale-Shapley algorithm that can employ a cryptographic primitive we propose for vector access with an arbitrary number of participants. Participants want to find a stable matching as defined by their secret preferences and without leaking any of these secrets. An additional advantage of the solvers based on secure simulations of arithmetic circuits is that it returns a solution picked randomly among existing solutions. Besides the fact that this increases privacy to a level of requested t-privacy, it also provides fairness to participants. A real implementation of a described secure solution usable by participants on distinct computers on the Internet is implemented (by students in a class assignment) and is available on our web-site.
BibTeX
@misc{eprint-2006-21836,
  title={Private and Efficient Stable Marriages (Matching)},
  booktitle={IACR Eprint archive},
  keywords={},
  url={http://eprint.iacr.org/2006/345},
  note={Full version of the ECAI 2006 Workshop on DCSP, Italy, August 2006 msilaghi@fit.edu 13433 received 12 Oct 2006},
  author={Timothy Atkinson and R. Bartak and Marius C. Silaghi and E. Tuleu and M. Zanker},
  year=2006
}