Improved Efficiency for Private Stable Matching

Matthew Franklin; Mark Gondree; Payman Mohassel

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2006/332

Improved Efficiency for Private Stable Matching

Matthew Franklin, Mark Gondree, and Payman Mohassel

Abstract

At Financial Crypto 2006, Golle presented a novel framework for the privacy preserving computation of a stable matching (stable marriage). We show that the communication complexity of Golle's main protocol is substantially greater than what was claimed in that paper, in part due to surprising pathological behavior of Golle's variant of the Gale-Shapley stable matching algorithm. We also develop new protocols in Golle's basic framework with greatly reduced communication complexity.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. This is the full version of an article to appear at CT-RSA 2007.
Keywords: stable matching stable marriage Gale-Shapley privacy-preserving
Contact author(s): mohassel @ cs ucdavis edu
History: 2006-10-05: received
Short URL: https://ia.cr/2006/332
License: CC BY

BibTeX

@misc{cryptoeprint:2006/332,
      author = {Matthew Franklin and Mark Gondree and Payman Mohassel},
      title = {Improved Efficiency for Private Stable Matching},
      howpublished = {Cryptology ePrint Archive, Paper 2006/332},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/332}},
      url = {https://eprint.iacr.org/2006/332}
}