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.
Category / Keywords: Publication Info: Full version of the ECAI 2006 Workshop on DCSP, Italy, August 2006 Date: received 12 Oct 2006 Contact author: msilaghi at fit edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20061020:100652 (All versions of this report) Short URL: ia.cr/2006/345 Discussion forum: Show discussion | Start new discussion